A database 'Nation' specific surely is the answer, its monitored, controlled and keeps the game within the period!
12K players..... great, Im sure the dev's like your prediction, lets hope for 24k, but ok 12k was plucked from the air... the English language alone has a million plus words. Im sure a hefty list could be created, along with their Spanish, French and Dutch equivalents. So ok have a limit on number of uses too, say each name can be used 3x which in effect turns 1 million into 3 million choices. Its not too uncommon either for ships having the same name, both the French and British navies had the same ship names eg: HMS Redoubtable for one...and ok on a list of 12k players 2 or 3 may have the same name, what are the chances of them being in the same battle, in the same sea zone, in the same ships? Even if it did happen I can live with a 20 gun ship being called 'Valiant' and in the same battle a 1st rater with the same name.
Moving on, so lets say 4 people want the same name.... 2 users are inactive, so set a offline time limit on names (agreed to in the T&C's). 1 month of inactivity and the name goes back in the pot. I'm sure people a lot cleverer than me can think of an effective method of registering and using a set of database names effectively..... But lets not stray from the ultimate point here, its about keeping this game unique, special, different from the ones that have come before and making 'Naval Action' different from the pack. Also you have to take into account that currently its a small team of devs, 4-5 I think. Adding cosmetic features may be at the expense of gameplay or some other equally important aspect of the game. Do you want customisation at the expense of gameplay? I dont!