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