If you are on a linux server that will let you support htaccess and you have a list of all the old page names you can set up what is called 301 redirect on all old pages to the equivelent new pages. for example
redirect 301 /old.htm http://www.you.com/new.htm
this will let the search engine know that the old page is permenatly gone and this is the new page.
Never tried it when the host has moved aswell and of course will ONLY work on linux where you can use .htaccess
Unfortunatly if you were on a windows server you need to edit every single page individually so changing host and unless you are on your own server will not be possible.
Other than that sitemap feed is way to go and ofcourse making sure all your pages are complient. Well worth doing a nice 404 page not found in your own branding, again not all hosts will allow you to do this but at least it looks better than a normal 404.
hth