It sounds like you did not do any housekeeping on your old hosting.

Because of the way the database index works at search engines, they use IP address as your 'ID' with your domain name and content being only secondary indexes.

If your old hosting still has your domain in the domain tree, then the search engines can continue to index that content - remember the http:// IP address/ ~username/ etc that can be used to access content before the DNS is moved? - if you could access the content then so can the search engines.

If the old site is still hosted there, it will continue to be found until such time as the host no longer responds.

The worst happens when the host starts to respond with a 404 response and then the old cache turns into a 'ghost' which can live on until the search engines cleans out its database - needs to replace the disk containing the database.

You need to ask your old host to give a gone response for all your old content. This is much better than a 301 response (OK in the short term until new host is discovered) as so many search engines keep the old url but just cache the new content on the old url rather than the new url, i.e. they treat a 301 response the same as a 302 response.

I hope the above helps get your site found on the new hosting.

__________________
There are gurus and there are the wise. The wise give freely of their knowledge, the gurus will try to sell you 'the next best thing'.