Putting a 410 Gone response on your old host is probably not the best solution, as this tells the search engine that this server is still the authoritative server for that domain name.
To prevent overburdening the DNS system with queries, most search engine spiders divert from the spec by caching DNS mappings. This cache is typically maintained for a set period (rechecked every month or so) or until the destination server stops responding to requests for that domain name. Typically, if the server responds with an error 400 Bad Request (this should happen very soon after you close your account - if you don't trust your host, you can always try to hack the response codes, but it may be risky), the first thing the spider will do is query the DNS system to find out if the domain name has moved.
Hacking server response codes:
The following entry in your root level .htaccess should force your old server to respond to queries looking for your home page with a bad request message:
Redirect 400 /
If that fails, you can always upload a php file containing the following:
PHP Code:
<?php
header('HTTP/1.0 400 Bad Request');
?>
<h1>400 Bad Request</h1>
<p>The hostname specified is no longer available on this server.</p>
<hr>
<p><i>Apache</i></p>
Also, again to repeat what has already been said, make absolutely sure that you are 301 redirecting the individual removed pages to the new locations on the new server. If a search engine sees a 404, especially after a move, according to spec this is a temporary condition. The search engines will keep looking for the content for up to a year. Longer if there are valid links to those URLs. 404 literally means that a resource is unavailable for an unknown reason. 410 should be used if the content is gone and will never return and there is no forwarding address. 301 should be used if the content is simply at a new URL.