>That is: does anyone know of a good public domain table (free or for that matter fee) that provides an extensive lookup of names by nickname, i.e. Charlie and Chuck = Charles, Bob/Bobby=Robert. As you can guess, we are trying to do smart searches and smart duplicate elimination.

http://www.nickname.com has this feature. Perhaps they might be able to give you a lead if you can convince them that you won't be in competition.