My vote is for http://faxzero.com/ Used them several times and all faxes have been successful.
If you need to send a document over in a pinch, take a digital picture of the document, crop it using Picasa, convert the image to a PDF using CutePDF, and send the fax using faxzero. A few more steps then going to the convient store although it all adds up to $0.
