wierd problem

I have a client who is having a problem with DNS. Most everyone can reach their web sites and send email, except those on attbi.com and rmi.net. For those people, dns lookups fail approximately 50% of the time. The domain used to be owned by someone who use rmi.net to host the domain. As far as I can tell, the gTLD servers return a correct response, and every other ISP appears to resolve the domain correctly. I have had no luck talking to ATT and RMI (earthlink) support (no surprise there). Any ideas how to diagnose this further.

Thanks,
Mitch

Doesn't seem weird, sounds like rmi and attbi have old authorative
data in their local DNS. Pretty easy to test. DIG or nslookup against
the rmi / attbi name servers and see if they return a different
authorative answer. If their server returns an old address you simply
need to get them to remove the zone info from their DNS.