As you probably know already, this is a very complex problem, especially when you are dealing with multipart names, non-western names, etc.

You may want to invest in commercial software that is designed to handle this problem:

http://www.softwarecompany.com/netgender-api.html