Dear Theresa,
Did you ever find an answer to this? I was doing a good search today and your post turned up in it. Birth certificates in New Caledonia are obtained through the mairie (town hall) in Noumea. They were very helpful when I was there, but I don't know about via mail. They needed proof I was related to the people for whom I was requesting documents. If you still need help, I know a number of people in Noumea doing genealogy and they'd probably be happy to help. Speaking or writing French would be helpful. :-)
Cheers,
Sharon
www.twocaledonias.net