I've got a design where my client vShield Edge's (5.1.2 build 943471) sit behind a second firewall that is actually on the internet. The outside interface of the Edge's are assigned a 192.168.x.x address. The second firewall performs a static NAT of that 192.168.x.x address onto a publically routed address. The second firewall does a permit IP any any with regards to the NAT'd address.
When remote firewalls attempt to establish an IPSEC VPN with the vShield Edge, they get gateway not found errors unless they turn off NAT-T. After disabling NAT-T, everything works fine.
Does the vShield Edge not support NAT traversal? I found some posts from 2011 that implied that it has problems, but nothing specific.