Address shows as "invalid" in checker


New Email
I've been using a business email address for 17 years:
I lease a dedicated server and manage it and the mailserver function myself. I must have something set up wrong.

According to various email checking websites, my address is either "Unknown" or "Invalid." If any clues are provided by these sites (usually none are) they are vague:
"We couldn't find this email address publicly available on the web."
"The SMTP server is taking too much time to respond."
"Retry Later. Transient Network Fault."

I can send to this address, and I certainly receive on it. But my server is constantly blacklisted by Microsoft, AOL, & ATT, but not Google.

I'm running cPanel/WHM on CentOS. Any guess as to where I should look in my server settings?