I'm no NAT expert, but some NAT devices can be configured to translate the addresses in SIP messages appropriately during routing. Linux IPTables has a SIP conntrack option (according to my Web search, it's in kernels >= 2.6.18) that does this. cisco IOS also supports it - I'm not sure when that feature was introduced.