You're on the right lines, yeah. On the wire, out on the internet, there is a packet with all the information we need to get through the easy/hard pair, but we can't access it.
According to the author of dublin-traceroute, it used to be that you could use ICMP TTL Exceeded errors to your advantage, because buggy NATs didn't translate ICMP payload (which contains the IP+UDP header of the packet whose TTL hit zero).
IOW, you could send a probe packet to the easy ip:port, with a TTL low enough that the packet expires somewhere between the two NATs, and listen for the returning ICMP error. Its payload would contain the public ip:port for your session on the hard NAT, which effectively gives you an accidental STUN server that gives you correct answers, even for a hard NAT.
I _believe_ this trick no longer works reliably, because the "NAT Behavioral Requirements" family of RFCs started laying down rules for what well-behaved NATs should do, and afaict, inexplicably, vendors listened. REQ-4 of RFC 5508 says that NAT devices MUST translate the payload of ICMP errors according to the appropriate NAT mapping, to preserve the end device's illusion that no NAT exists. So, these days, the ICMP error you get back contains the unhelpful LAN source ip:port :(
I still want to experiment with that some more, because if it's unusual but not unheard of... Well, it's another technique to grab a little bit more of the long tail :)