I have limited exposure to T.37 (store and forward), so I can't really answer to that question. I guess what happens is that you negotiate in realtime with a fax-like entity running on the media gateway that your cable box is sent to, and that later your fax is then sent along to another media gateway which then negotiates with the fax machine you're sending to. Sort of like fax by proxy, with two actual fax calls being placed (one between sending fax machine and gateway 1, the ohter between gateway 2 and receiving fax machine) - rather than one call between the two fax machines.
Try to nail them down on what they mean by "FoIP". This typcailly means "fax relay" in the business, not just fax over G.711 (which is usually called "fax passthrough"). There are other flavors of fax relay that are not IP-specific - there is fax over AAL2 (for ATM Links), FRF.11 (for frame relay links, largely obsoloete) and other proprietary methods. However, what I believe that they're doing is blowing smoke up your rear end. I bet they just sense the tones on the line that are unique to fax, and switch your call over from a voice-specific codec (like G.729ab) to G.711. If this is the case, as I've said before, there is no reason you should not be ablt to use your PC w/ modem at 14400bps speed - unless their network sucks.
Ask them this specifically: "Does your fax solution implement true fax relay (FoP), or is it simply fax passthrough, with G.711 carrying the fax traffic?"
James