If your site is on a different I.P. then it takes time for the index bots to find your new site.
This is not likely caching, but it could be that you have a robots.txt file that is getting in your way, Have you verified that the robots.txt file is not filtering any search engine bots inadvertently?
Did you have your domains active on both the old shared server and new VPS? You could be getting penalized for duplicate content on two different domains.
You would've been well served to 301 redirect your old site to the new site, but it may be too late for this.
In time (if getting penalized for duplicate content) the bots will learn that you are no longer duplicating content and should remove the penalties.