Very but as with the example he is giving, this is very useful technology for video games where hosts and clients are regularly behind NAT. UPNP has made this somewhat better but it's still no where near perfect.

If i'm not mistaken, much of the UDP punch-through technology was invented by Skype. However, skype still relies on a proxy server that every client connects to. It needs that so that the client can prepare the router to let data through from a certain client IP. These guys here found a ridiculously clever way of skipping this step which makes true P2P with both end points behind NAT possible and even easy to implement.

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. 

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.

Better just to block all ICMP TTL exceeded packets, breaking traceroute entirely. Normal users don't use it that much. Traceroute sucks; it's clunky, slow, and unreliable. Network people need it (and they can carve exceptions for themselves), but end-users don't.

All of these techniques could be prevented if you knew about them.

Yet I wouldn't be surprised if the specific IP address wasn't customizable eventually when you control both sides.