First ping (to any destination) fails from switch but not from router

I've got a basic network setup, just doing NAT to a single public address to an internal /24 without any VLAN's or fancy routing.

Both my router and switch are running Cisco IOS 12.x. My configuration is very minimal. Here is the problem:

From the router, I can successfully ping any device on the local network or internet without any loss.

However from the switch, or any device connected to the switch, the first external ping will always fail.

Any suggestions?

Below are some examples of what is driving my curiosity.

From a Linux host on this network:

#ping -c 5 4.2.2.1
PING 4.2.2.1 (4.2.2.1) 56(84) bytes of data.
64 bytes from 4.2.2.1: icmp_seq=2 ttl=55 time=9.11 ms
64 bytes from 4.2.2.1: icmp_seq=3 ttl=55 time=10.1 ms
64 bytes from 4.2.2.1: icmp_seq=4 ttl=55 time=10.8 ms
64 bytes from 4.2.2.1: icmp_seq=5 ttl=55 time=9.80 ms

--- 4.2.2.1 ping statistics ---
5 packets transmitted, 4 received, 20% packet loss, time 3998ms
rtt min/avg/max/mdev = 9.115/9.981/10.831/0.625 ms

From a Linux host not on this network, not using Cisco gear, but with a similar network topology:

#ping -c 5 4.2.2.1
PING 4.2.2.1 (4.2.2.1) 56(84) bytes of data.
64 bytes from 4.2.2.1: icmp_seq=1 ttl=59 time=6.16 ms
64 bytes from 4.2.2.1: icmp_seq=2 ttl=59 time=3.56 ms
64 bytes from 4.2.2.1: icmp_seq=3 ttl=59 time=5.45 ms
64 bytes from 4.2.2.1: icmp_seq=4 ttl=59 time=3.24 ms
64 bytes from 4.2.2.1: icmp_seq=5 ttl=59 time=4.22 ms

--- 4.2.2.1 ping statistics ---
5 packets transmitted, 5 received, 0% packet loss, time 3999ms
rtt min/avg/max/mdev = 3.242/4.529/6.160/1.115 ms