We have a 2811 running NAT between 2 FE ports (1 inside, 1 outside) and several serial (inside) and the same outside FE port. There are ~100 static NAT entries in the table for devices that need a specific identity on the outside and 1 pool to catch any addresses that don't. Periodically, one of the static NATs will fail. This device hosts a number of things including DNS for the inside and RADIUS from the outside so we know when it can no longer access the outside in short order. If we check the NAT table with show ip nat tr, there are a number of dynamic entries for the device but there is no ARP entry on the outside when we show ARP. If we remove and reenter the static statement, the ARP shows up when traffic is passed and everything works again for days or weeks.
The router is running IOS 12.4(15)XY2 ADVIPSERVICESk9. We plan to upgrade it in our next available maintenance window but see no release notes in the earlier releases relating to an issue such as we are seeing.