Exchange server not receiving some email

I'm not an exchange expert by any means, but I know very basic things. I've run into an issue with a client and they are nto receiving emails, but only from various domains. I don't know the full list, but namely, msn, hotmail, comcast, aol to name a few. I can email them from my company's exchange server no problem and it goes through almost instantly. If I email them from my comcast or gmail account, the message never makes it through. I checked the smtp logs and I can identify, for instance, the comcast servers trying to connect in ... but all the log reports is quit - 240 at the end of the line of the log from comcast. Various places can send emails to them successfully, but others, like comcast, aren't successful. I've replaced the modem, bypassed the barracude spam/firewall, I can telnet to port 25 on their mail server (quickly, too), I can send from their server no problem; I did various mx record lookups and mail server health checks and I don't see any problems anywhere ... except that various places cannot email them successfully. I even recreated their virtual smtp server incase something was corrupt, but it did not fix it. PLEASE HELP!!!