DNS Mess

Hello,
So I have a server cluster that was 3 computers. A DC, Mail, and Web server. The Web site was recently moved to an off site service so I shut it down. I changed the A records for the DNS hosts and the IP in the Hosts files on the DC and also in the DNS zone file. Both servers (DC and Mail) can see the new site, but all the computers around the office still see the old site and IP. How can I change this? I cleared browser caches. Also is this a problem for bookmarks that customers have and how long does it take Google to change.
Thanks,
Mike