I just got the mail() function to work on my system (Windows2000, Apache 1.3.20, PHP 4.0.6) and it has been working fine. An example of my code is as follows:
<?php
mail ("scottrtucker@hotmail.com", "$subject", "$body", "From: $email\nX-Mailer: My PHP Script\n");
?>
$subject, $body, and $email come from an HTML form.
I would like to see your code if it is different. I don't see anything else in the setup besides the name of the SMTP server that would cause any trouble.
Hope I can be of some help,
~Scott