1) Make sure port 25 is accepting connection to everyone except some open relay hosts where you can deny them explicity or use RBL.
2) If your SMTP server is not SSL/TLS-aware, make sure you have disabled it in your email client
>> If I am on the Linux box I can send mail
For your Linux box to send outgoing messages to remote hosts, it doesn't even need to be running a SMTP server at all. Imagine you launch telnet and connect to port 25 and invoke SMTP commands manually, the other end doesn't care if you are running a SMTP server.
>> But I can receive mail that was sent from the linux box to itself using the windoz box
Port 25 doesn't take place at all. Checking your mail, say pop3, that's port 110, and it has nothing to do with port 25.
Don't ask me how to configure Sendmail, because I don't know or care. Sendmail is on the top 5 of most insecure software list (BIND, Samba, webmin and wu-ftpd being the others). Redhat as well is not so secure. Running an out-of-date version (8.12.1 being the lastest) of Sendmail on Redhat makes it extremely insecure and potentially vulnerable to local and remote exploits at any time.
Then who makes the most secure software?
DJB-ware -> http://cr.yp.to/djb.html