Thanks for the input everyone.
I generally agree with the idea that fax is obsolete which is why we moved to scan/pdf some time ago ourselves, but because it is entrenched we still have to support it both ways for communication outside the organisation.
Regarding fax over voip specifically - I am really just after a centralised fax to email service which removes the need of a local phone lines at each office. Basically the BizFAX type device that supports 10 numbers with separate routing for each number (and preferably without administering it ourselves... but I will look at bizfax).
Regarding compatibility - over the years we have had many issues with general fax machine (in)compatibility on PSTN anyway, especially when receiving faxes from fax advantage and the like. I don't have a big problem if it doesn't work, but like I say, it is a problem if the sender thinks it worked but we didn't receive it.