Well, it's pretty annoying but you can do it. Read about the STUN protocol, and especially the part about the different kinds of NAT. The jist of it is that there are some devices that will always map the same IP:port of a UDP packet to the same external IP:port, and will also forward incoming UDP packets to the correct internal host if it has seen packets from that host in the recent past.
But yeah, sometimes you're just screwed and need to fallback to TCP.