The issue of names will be a complex thing until we don't know how the game world is going to be established.
For example, in encounters which rememorate real battles (Trafalgar, for example), would be easy the work to give to each player a name for his ship. Simple: there will be a list of available vessels that took part on in the historical battle. People who played Privateer's Bounty Age of Sail II will know what I talk about.
But the real problem is when there is a opened world server. A solution would be, as other ones have said, making a database of registered possible names. Players send a request to servers administrators applying for the acceptance of a new created name. Those persons will check each name according to good faith and morality, and after that they finnally decide to deny or admit the requested name.
This solution is, in my understanding, subjective and relative. For example: One person request to administrators the admission of the name "Pennies" which allow him to put on his vessel. Well...some people will think, first of all, that this guy is trying to strain a name with dubious morality that make reference to the male member in the game. The administrators refuse it, but this guy plead that his name is refering to, simply, the plural of penny (coins).
This measure I think could not be efficient enough due to there must be a person (or persons) who are going to check, every hour, every day, every month, solicitudes of possible names that he has to accept or deny, and answering with every dennied name the reasons of why it was dennied.
I propose a different solution, maintaining the base of a database:
There could be a database of: Names of persons, animals, plants, colours, cities, etc; allowed adjectives, adverbs, conjunctions, prepositions, articles, determinants, that will bring us the possibility to mix/combine them to make a new and personal name. Special characters will be refused. In the case of a person makes the same combination of words than other one, will prevail the older combination. For example:
I would like to name my french frigate with a beautiful name. I'm going to choose the name of a plant, a preposition and the name of a flower: Fleur + de + Lis --> Fleur de Lis.
We can add also restrictive limits like no more than 4-5 words, and the possibility to use capital or non capital letters.
I believe that the main problem of this way to give a solution for the issue of names is the language, that will be necessary to have a database of many different languages: french, spanish, portuguese, italian, english, swedish, danish, german, polish, russian...
That is what I think.