It is worse than that. The STUN taxonomy is brittle, there are NATs which feature different behaviour than anticipated in RFC3489.
Right. There is one we like to call the crap-nat. This nat changes the source UDP port every few seconds. So once the media flow is established it only works for 2-3 seconds until the nat switches to another source port. Needles to say there is absolutely no way to make VoIP work unders these conditions. We encounter one of these every few weeks, and the only solution is to have the customer change the NAT device he is using. (these are usually ADSL modems with inbuilt router)