Did you try setting your fax machine to 2400, 1200 or 300 baud and turn off ECM (error correction) ? That should help. As for Vonage you just got very lucky. I used to work for them and (other then the suggestion above) you were SOL. They didn't "support" it either. They would do some ATA tweaks but would tell you up front that it will affect your voice service negatively.

That being said, VOIPo offers free OUTBOUND faxing from documents which works well. It's in vPanel and their inbound fax number is only $24 for a year and also works well. Actually better than a fax machine even when it works.