ARP caches on boxes you dont control != fun
The problem:
Cisco ASA was swapped in for a SonicWall firewall. The ASA had a known-to-be working config, and outbound NAT was working but inbound sessions to a mail server that had a 1:1 nat on a different ip that the outside interface of the firewall were failing. After looking closey we realized about half of the static nats were working - you could ping the static nat ip and access tcp services that were allowed via the acl. In front of the firewall was a managed router - the ISP had restricted all access to the console/telnet/ssh on the router.
It appeared that when the ASA replaced the SonicWall (same ip address on both) as part of its power-up process the arp-cache on the router was updated with the new mac address so the ASA's outside ip address was working fine. The static NATs that had recently been associated with the SonicWall MAC address were "stuck" in the router arp cache. The inbound mail being the most common traffic for this network the mail server static NAT had certainly been just in use as the firewall swap was done.
Perhaps the ASA needed to issue a Gratuitous ARP for the static nats that it operates. This probably would have fixed the issue if the router was not setup to ignore them. Anyway, rebooting the router "fixed" the issue which is a problem, since it encourages the behavior of "if its not working yank the power cord" mentality.
Another solution would have been to unplug the router ethernet interface that was facing the ASA firewall. The arp cache should have been cleared when the interface went down, which should force it to re-ARP for the static nats when it was plugged back in.
According to cisco the ASA should issue a Gratuitous ARP for the static 1:1 nats when they are programmed. I tried removing the 1:1 NAT for the mail server, and re-adding it, and still it did not work (ASA was running 8.2.2).
Here is more info on Gratuitous ARP:
http://wiki.wireshark.org/Gratuitous_ARP
"A gratuitous ARP request is an AddressResolutionProtocol request packet where the source and destination IP are both set to the IP of the machine issuing the packet and the destination MAC is the broadcast address ff:ff:ff:ff:ff:ff. Ordinarily, no reply packet will occur. A gratuitous ARP reply is a reply to which no request has been made."