I did some shopping around and picked myfax.com.

I pay them $10 a month (for the last year now) and haven't had one problem sending/receiving faxes as PDF attachments in emails.

On top of that, the phone number they gave me is a toll free 888 number so my business looks like it is really important with a toll free fax number.