I wrote the underlying networking layer used by Battlezone,
and am happy to report that the latest patch (1.3?) will
support some firewalls. In particular, it will support
any firewall that uses only the remote address/port pair
to look up the inside address/port pair.
Unfortunately, Linux's IP Masquerade uses both the remote and the outside address/port pairs to look up the inside address/port pair. This makes any sort of peer-peer gaming impossible.
I will put information on this issue at http://www.alumni.caltech.edu/~dank/anet.html when I get a chance.