Users still not getting registration email

Greetings,

I have spent two days reading old and new posts on the issue of a user not getting an email once registered.

Statistics:
We host our own site Windows 2003 R2 Machine
We host our own mail application (Mail Enable)
The admin email address is set up in the mail program
Version 2.5.1
Clean install
Email is active on PHP we have other emails and forms are working great
Admin email gets the new user email
With various plug ins still get the emai

“The e-mail could not be sent.
Possible reason: your host may have disabled the mail() function…”

Is this a bug in 2.5.1

Any help would be appreciated. If you need more information please let me know. This is very challenging especially since PHP is letting mail pass in other areas of our site.

Thank you in advance for your assistance. This program is great if we can just lick this pesky issue.