Is it possible that you have voice mail messages during the other times that you have attempted to dial out? Telcos will frequently provide a stutter dial tone when a voice mail message is waiting, and sometimes a modem will not detect the stutter dial tone as dial tone.
As an alternative, you can configure the modem to ignore dial tone prior to dialing, but that leads to some different issues that you probably want to avoid if possible.
pansophic