Success! The entire problem was my fax line provider. I had to argue with Tier 1, Tier 2, and finally was given a special fax line engineer (apparently).
The fax line was from our phone system provider (VOIP), through a Cisco ATA box. I was told by the first 2 tiers of engineers that the issue was with my own network, because when the fax line was plugged in directly into my Brother fax machine, I was able to receive and send, but when I tried to use any other device (usb fax adapter, cimfax server, etc) faxes were either not coming in at all, or taking forever to send/receive.
Note to self in the future: When I feel like I'm right, ignore the techs and just annoy them until they escalate you.