if it's sending packets on a dance through a virtual network, why does that have to use public addresses? would using a private network (eg 10.0.0.0) not have worked? why not? (and is it odd for people to still have unused /24 lying around?)
Secondary reason: To prevent IP address spoofing, many routers have "reverse path filtering," which drops packets with source IP addresses that shouldn't be coming from the interface they're coming from. This would put a stop to the ICMP TTL exceeded messages and you'd just see stars in the traceroute output.
There is a surprising amount of unused IP address space out there, which can happen when, for example, an organization has a large allocation and they're not using all of it. This is kind of unfortunate but there's not really a practical way to take small amounts of unused address space and make use of it elsewhere on the Internet.
Edit: By the way, that wouldn't have worked for this hack anyways, since you wouldn't be able to control reverse DNS for the private IP addresses.
The real problem is that an ICMP Time Exceeded packet coming from behind NAT would presumably either be blocked by the NAT or else have its address changed to the routable public interface of the NAT device. If the packets are dropped, that would obviously be a problem. If the IP address were changed to that of the NAT box, then all of the reverse DNS lookups would have the same result.
By the way, some traceroute implementations use ICMP Echo Request packets instead of UDP.
Edit: punctuation