Cannot reach certain mail servers

[Sysadmin]

I have recently noticed a growing problem and am curious if anyone else
is seeing the same.  There are certain email servers that I am not able
to reach.
  I get a "read timeout error"  I used the standard 'telnet mailhost 25`
to troubleshoot and found that I am able to reach certain site just
fine.  That being I get the RFC required banner.  While others I get
nothing. It started out as some .gov sites (e.g. fernald.gov). But now
we are unable to reach AOL.com as well.
  I have even gone as far as looking at the packets with a sniffer.  I
DO find differences.  The response coming back is different.
  The REAL kicker is that the results vary by OS and connect type, 

RH8 - LAN connection - doesn't work here but does in another geographic
location
Windows XP - LAN - 2 different locations - doesn't work
Windows XP - Dialup - works
MAC OSX - LAN - Location 2 - works

The server used for the test case is running Sendmail 8.1.??.  I am
running postfix 2.0.19 on Redhat 8.

Anybody seeing this or have any ideas.