Google doesn't immediately re-index your site on-demand. They do it when they choose to do it. And they don't always pick up your submitted site-map immediately either.
The correct approach is to make sure that anyone (including google) gets a proper 404-not-found response when they hit those "old" pages.
Your hosting company can help you sort out whatever is preventing Google from getting a 404 correctly (ie: perhaps you have some weird rewrite rules going on that send visitors to some other place instead of properly giving a 404-not-found.).
As far as Zen Cart goes, if you were talking about old "pages" within Zen Cart (such as non-existent products, or Zen Cart content pages etc that you've removed), then Zen Cart would send a proper 404 response.
But you seem to be talking about pages from the site from before Zen Cart was used, so it seems like it's some other issue you need to sort out outside Zen Cart
.
Zen Cart - putting the dream of business ownership within reach of anyone!
Donate to: DrByte directly or to the Zen Cart team as a whole
Remember: Any code suggestions you see here are merely suggestions. You assume full responsibility for your use of any such suggestions, including any impact ANY alterations you make to your site may have on your PCI compliance.
Furthermore, any advice you see here about PCI matters is merely an opinion, and should not be relied upon as "official". Official PCI information should be obtained from the PCI Security Council directly or from one of their authorized Assessors.