I have a TeamCity server set up behind a NAT firewall, but with the servlet port forwarded through the firewall. I have one agent running on the same box, and I have access to a number of other machines behind a different firewall elsewhere on the internet.
From what I can tell, the agents need to be exposed to the internet in order to interact with TeamCity, so that they can receive instructions from the central TeamCity server.
Have you considered implementing an approach that would allow agents to be fully behind the firewall? This could be implemented via a polling strategy, where a given agent polled the TeamCity server every minute or so for instructions. Clearly, this would be much chattier, but would make WAN-based deployments across disparate organizations much easier to set up.