Yup i'm using mainly geonames.org for references... beside being the source for a lot of other map sites (mapcarta, toporama, itouchmap, and a lot of others) it allows users to correct positions (some places are slightly out of position, due to having been initially entered with the only available source, degrees-minute, and therefore up to 5-10km out of target) and to add aliases, historical names or missing names.
The interface is not perfectly user friendly if you use the map to visually search (it has little glitches - like when you're searching something you're automatically zoomed in and unless you clear your search you're not able to zoom out), but if you know the general area the ship is in, i found not too difficult (and sometimes quite fun) to find a specific place.
For text searches i'd say anything could do the trick as long if comprises points, islands and geographical features (the esri arcview with autocomplete seems pretty nice indeed, though old historical names are probably not comprised)... for visual searches mapcarta (my previous preferred source for reference) is probably more user friendly, but does not allow place editing, and existing places are updated from geonames more or less monthly.
Specific areas have some specific resources... Canada is pretty well covered by Toporama, while US and Alaska are nicely covered by EarthNC (NOAA maps in transparency over google satellite view).
If you can read cyrillic, Loadmap covers almost the whole world and has Russian Army detailed maps (up to 1:50000) over google maps view (no trasparency but overimposed maps can be turned on/off)... it has solved a couple of pretty tricky situations.
The main missing resource at the moment would be some detailed Admiralty charts for China names... those are indeed terribly difficult to work out