That is partially incorrect, STUN can punch a hole through even when both sides uses NAT in many cases. That is what I would classify as STUN’s main feature.
From the network point of view it looks the same as two hosts starting an outgoing TCP connection through nat - if that works then hole punching should work too.
Some are trickier than others, as there are 2 IPs and 2 ports in a packet (at any point), and it can be hard to match all of them for the stricter devices, esp. on NATs that do source port randomization.
Those are called "middleboxes" (IIRC) and they're unfortunately somewhat pervasive.
You send outgoing packets simultaneously from both sides. Causing both sides to add nat translation entry’s to their nat tables. When the packets arrive both sides already have nat translation entries and the packets go right through the nat.