[ale] Blacklisted mail server?

[ale1 at cybertechcafe.net (Nathan J. Underwood)]

A client of mine has recently started using Cbeyond as their ISP.  Since 
the cutover, they've had problems sending emails to random domains. 
After digging around a bit, I've found that they seem to be blacklisted. 
    The error messages that the users are getting were pretty generic, 
so I started digging further.  My first move was to ping the server 
reported as the primary MX for the recipient (got a response).  I then 
tried to telnet to the mail server (i.e. telnet mail.server.net 25), and 
got an immediate connection refused.  I then tried the same exercise 
from my ip (not blacklisted), and was able to connect.  They're not an 
open relay, and I've not been able to find any lists that their listed 
on.  Anyone got any suggestions on where to look next?

-- 

--

registered linux user # 73046