My limited experience matches Kev’s: receiving UDP responses is no problem if they come from the same machine I sent the request to, and within a minute of my sending the request. It’s easy enough to send ‘keep-alive’ packets to stop the mapping being lost.
If both client and server are behind this kind of firewall, then yes indeed you’re stuffed. For this reason, UDP is useless for peer-to-peer phone games, at least if the NAT/firewalls behave as my operators’ do (highly probable, I think).
But if the server is behind a firewall that you’re able to configure (e.g. that on my home machine), you’re typically able to specify some fixed UDP ports that don’t get mapped, and then clients can connect to your machine no problem.