Mail problems....a funny one!

I run W2K with PHP4 (4.0.2). I have a certain script that generates an email message from a form on a web page. Works just perfectly from my local system. If I upload the webpage onto my Host - nothing happens. Everything looks and feels like the mail has been sent - but really nothing happens. ie, I press the 'send email' button, and everything looks ok - but no mail every appears in the mail box. I have put phpinfo() into the script. The version locally is the same as what is on the host - 4.0.2. I have looked through the variables shown by PHPINFO and can see nothing too different between the local machine and the host. We are talking about the mail() command here. Every other PHP function seems to work just fine locally and on the host. Does anyone have any idea what I should look at??