Note that any NAT that drops UDP packets altogether will basically disable DNS and VOIP type applications or at least degrade the experience in serious ways. I haven't come across many such NATs recently.
Another point scored for TCP in TCP with an SSL VPN. :-)
(I do keep a TCP VPN running on port 443 ready to go for these situations, but UDP is always my first choice.)