Thanks for the help. Yes, I had run a DNSreport and there were a couple lines where it failed, but the host insists everything is OK. Running the DNS Timings for A and MX shows an A+ and ISP Cached DNS Lookup shows one cached entry for the wrong DNS. So yes we did also change the DNS host although I had already updated the old DNS host info in case this happened, but the old DNS host is still giving out the old records and many ISPs are still looking to that host for our records. So I think the short term solution is to get our old DNS host to update their records as requested 5 days ago!

Stu