Hi,
several ways to get an idea what might be wrong:
If you have shell access (ssh or something like that):
Log in and try to send a mail with e.g. mail:
mail -s Test myname@thedomain.com
Then type some message and finish with typing a . on the next line. Then check if you got the mail
Second, post the code you use to try to send a mail, but the code shouldn't be the problem since it already worked.
If the hoster can give you the host name of a mail server you could even try to use one of the SMTP classes downloadable from php libraries like the one on phpbuilder.com.
One problem might be the setup of sendmail, but I would need to see the sendmail.cf in order to tell you anything about possible problems.
Does the hoster use sendmail and Unix/Linux as server OS at all ?
If the SMTP relay is open but sendmail isn't configure correctly then mails might be rejected by external mail servers for delivery.
Thomas