Also, some hosts require that, in order to send a message, the account being sent from be registered on your webhosting account; so if you're using external email you'll want to be sure the address exists on your host.
An example would be if you send mail as "noreply@example.com" it would need to be an account on your hosting server. All webhosts are different, but this is something that you could check.
Some servers also don't send mail out as it is sent, it is placed in the mail spooler with a delay; BlueHost is one such host, messages can take 1 minute or 1 hour to send (I'd assume based on how many messages are sent per X period).
