It seems that the only two New Caledonia cities that Tableau's native maps recognizes is Dumbea and Noumbea. So you will need to use independent lats/longs to populate your map. As to your cities in the water problem: I've found Tableau's display of lats/longs to be very accurate (of course I don't do work in the south Pacific). While I've never used Google Earth for lats/longs, I have used Google Maps many times without any problems. So my first inclination would be to double-check the accuracy of the underlying data, and maybe try getting the water-cities from Google Maps instead of Earth.
If you post the csv file, I'd be interested in taking a look for you.
I looked at other sites in order to get correct Lat and Long coordinates and finally found that the coordinates from :
http://www.gpsvisualizer.com/geocoder/ to be perfectly accurate. I didn't compare the coordinates with Google Earth but all my cities now display perfectly.
Thanks for your help.
Alexander, thanks for the link! I'm always on the lookout for batch geocoding sites. I'll try this one out.