The phone line would only be an issue if someone picks up the phone. If a call comes in it would just get an engaged signal and the fax would be none-the-wiser.
I don't have material to reference you to, but this was the most common problem whilst I was working for one of the major companies that made fax machines.
The only other things I could suggest would be to:
1. Do a MOLDS test (Or equivilient in your country) on the line and see if there is any interference, get the other company to do the same.
2. If you're routing through a PABX, check with the manifacturer if there are known issues. Otherwise, check anything on your side of the demarcation point for wiring faults, excess cabling. etc.
3. Set your Fax machines to a lower speed. There may be an issue with autonegotiation if the equipment is running newer proprietry fax modem technology. If they are both G3/G4 compat, there shouldn't be a problem.
4. Install a dedicated fax line.