This is a tough one - not technically, but rather because my own experience, and that of others, points to a real problem here.

If your host is unwilling to implement 301 redirects for you (to cover the non-www to www redirections, for example), there's little you can do, since you have zero access to the server.

Get as upset as you like that they DON'T provide this basic service, they likely won't care. One solution is to find a host who's willing to work with you on this stuff and move to them. Another may be to embed 301 redirects directly into each moved page. This requires leaving old pages up, though, and is not the best way to handle this problem.