Found out what it is!

We took the fax machine completely off the system, connected it to a copper line and sent a bunch of test faxes - it was still silencing the calls, but not as frequently (one in every 15 or so).

Turns out that the vendors lines are bleeding / back-feeding through each other.

We disconnected all the copper lines from the system, sent faxes through the one copper line and bingo! No problem. Reconnected the lines and it happens again.

We've got the vendor coming out tomorrow to start checking their wiring.