Hi!
There is an excellent articel about the various NAT implementations in the current issue of the Internet Protocol Journal: http://www.cisco.com/warp/public/759/ipj_7-3.pdf
There you will find the background info to your NAT problems ;-)
cheers, klaus