I have a Pretec 56K Pocket PC CompactModem, which I bought on Ebay for about 10 pounds (That's about USD $18 to our colonial friends). It worked straight out of the box for PPP and sending/receiving faxes (with efax). I find it indispensible when travelling.
I have a Bluetooth card too but I find it more fiddly to get the connection up, so for ease of use I prefer the modem.