Fax

The other end should not matter whether it's a fax/modem or stand-alone fax machine. Your problem really sounds like your dialing properties are messed up. If on an internal phone system, your computer may be leaving out an initial '9' when a 9 isneeded, or vice-versa, or presence/absence of an initial '1', or something along those lines. I'm not sure what software you're using, but verify that the dialing properties match your location, and verify by attaching an analog phone to the phone jack on the modem itself, and see if you can dial from the phone and get a modem training signal from the other end if you dial the fax number properly.
--Charlie