All email accts: The account or domain may not exist, they may be blacklisted...

[sh4ka]

The account or domain may not exist, they may be blacklisted, or missing the proper dns entries.

This is the error I got on almost every domain at the server.. it started today and it is happening on almost every email account we host on different domains.

Tried reinstalling exim, changing resolv.conf nameservers and the error stills.. What can I do?

Im using RHE 5.2, and lateste Release tree.

Thanks.