I've had the issue as well in the past. I always connect into the server and drop to DOS and do an IPCONFIG /FLUSHDNS if I know email used to go to another email server and may be cached.

Thanks for the suggestion John. I gave it a try and then tested the results in CMD window, it is pulling the correct MX when I query the domain, however, in the web UI when trying to set it up, I still get the error. What IP address could it be looking for?

 

I'm wondering if the services need to be restarted? I would hope not, and I haven't gone to that length yet.