Which fax method is configured? T.38 or RTP pass-through?
If you use T.38 see this note:
Outgoing T.38 fax through symmetric NAT routers WILL NOT work, since the external called party is responsible to start communication with the fax answer tone indication. On the other hand the external endpoint must wait for the internal endpoint to send a T.38 packet in order to know where to send the fax answer tone indication (source wiki.innovaphone.com).
Regards.