[d4rt]

On most firewalls this should be trivial. On an Cisco ASA:

access-list BLOCK_TIMEEXCEEDED deny icmp any any time-exceeded

(iirc) and then apply the acl. You should block all hosts as any could be chosen by the person. They could change 3.3.3.3 to any other IP.

NAT is not a security mechanism and does not ensure your hosts are protected. Denying tunneling of any kind is difficult as there are tunnels over most protocols. I'm not aware of any perfect prevention or detection technique, but detection could in the case of a moderate amount of data transit could possibly be done via analysis of netflow records. 

[tophercyll]

And in fact they almost certainly will choose a different host. Our plan is to just buy an extra IP for one of our VPS machines and leave it unused.