But the packets aren't addressed to the intermediate routers. All of the packets are addressed to the endpoint, with a TTL value too low to make it there. The intermediate routers just reply with an ICMP Time Exceeded packet.

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

But you don't really need a route TO it? Would it technically work to start sending replies back with private IP addresses in the middle of the traceroute? Or do most ISPs filter those even in the replies?

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.