Nice original case :)
The question is about the method to store, yes, but mostly access the data.
The text storage you are using is fast, and you should keep it in my opinion, for low number access (1-100/sec).
If you need to pull a lot of data at once, like a thousand names in a tick, I would try to go for a database. SQL could help select the right names, and give you back a list in the same format (1 name per line) but you could just use ALL the names, and not seek the first, then the second, ... effectively speeding the algorithm a lot. (explode is a lot faster than 1000 seek ^^)
But isn't there another way to use/reuse the names ? Why do you have to pull thousands of names at a time ? Could you imagine load those 1k names over 1 to 2 seconds, displaying a loading bar during this ?