Stale DNS Issues

I use DNS made easy for external dns.  I had a record pointing to a server in my environment from DNS made easy.  It was working fine.  Now i have moved the location of server to the cloud and changed my DMSMadeeasy.  I can ping the IP address from my network, but cannot ping the web address.  I removed the old record from my internal dns and have waited about 7-8 days for it to clear.  I continue to get  "Ping request could not find host www3.advance-trading.com. Please check the name and try again."  If I edit the host file on my pc and put in the IP address where the web address points it will work.  Any ideas how i can fix this so i don't have to edit host files for everyone?
Using:DNSMadeeasy, Windows Server 2003, and SonicWall Firewall