As Robert pointed out, fax over VoIP is just really sensitive to any sort of call quality issue.
If you're willing to pay for a new fax machine, a much better option is to not use a fax machine at all. Get with the 21st century, and use an inbound fax mailbox.
For example, you can get a free or paid inbound phone number (a "DID") from Callcentric, and route inbound calls to their fax server. It will then store the fax and optionally, email it to you. This is far more reliable than using a fax machine, which suffers from the long chain of analog<-->digital<-->analog<-->digital conversions.