Remember that a modem just turns the data into audible modulation. You're at the mercy of whatever voice compression codec the provider uses to make sure the carrier tone doesn't drift so badly it generates erroneous bits and the faster the modem speed the quicker the modulation and again, it's up to the CODEC to be able to differentiate between a difference in 200hz. I really can't recommend services. You'll have to ask someone more experienced than I am with this but all the bluetooth to cellular bridges I've used so far will NOT work.

I've always been told to get a Panasonic 308 PBX. They are a little old but supposedly cheap, plentiful and you don't need special phones to use it but while the CCTALK mailing list has said they are usually $20 each I've yet to see one for less than $100.