Most modern data-capable phones will act as GSM fax modems. But few
PAYG networks support fax. Only Voda and Virgin do (to my knowledge; I
have tested both). Orange certainly don't. Voda support incoming fax
too but you have to contact them and get a different receiving number
allocated. I have no idea if Virgin support incoming fax.

Fax is one of the things that operators use to differentiate contract
from PAYG. Port blocking is another. Roaming is another. If they
didn't cripple PAYG then a load of business users would move to PAYG.

Fax is more widely supported on contract SIMs.

I am afraid that trying to get faxing working via a bluetooth
connection is a bit like trying to eat a 3 course meal, with
chopsticks, while hanging upside down :) Just getting Winfax
configured to work with a GSM modem is a job in itself; the tinyest
detail has to be just right. I have v10.02 working with a Voda SIM,
but this is with a PCMCIA card, a Sierra 750. The new GPRS/3G cards
are made by Optima and don't support fax at all.