Nocturnal, fax over VOIP will, depending on some details, work none of the time, some of the time, or most of the time. Faxing over VOIP wil not work all of the time. In order to make it work all of the time, you need to be doing real fax over IP, where the equipment on each end of the connection is participating in the fax protocol and helping adapt it to an IP network. There are a few different ways to do this, T.38 has the most mind-share but I believe it won't work if the connection has too much latency.
As far as I know, none of the VOIP providers currently deploy any of the fax over IP assists, so you're stuck with, at best, working most of the time.
Some VOIP providers offer fax<->email gateway services, I would recommend you investigate those. Or some other web/email<->FAX service provider - like EFax, but don't use EFax themselves.