ideas for switching domain names

My boss has two websites that are hitting pretty well on the search engines and he wants to change the domain names on them. Currently, the domain names are really long, but the titles of the websites are shorter and sweeter. We've registerd the titles as new domains and we want to switch all the content over to the new ones.

I know how to do that pretty well, but does anyone have any suggestions for doing this without losing search engine rankings? The boss said something about a 404 redirect on the old domain name pointing to the new one. However, he wants to just have our host point the site to the new domain. He thinks that this will automatically send people who click on the old domain to get to the new one automatically, the search engines to keep all the info that they've crawled from our old domain and apply it to our new domain.

My thinking is, wouldn't I have to keep the old site hosted out there in order for them to get any kind of redirect script? I know that I most likely can get a redirect script through the people that we registered our domain with, but that would only handle redirects for the main page (URL) wouldn't it? It wouldn't handle redirects for sub pages (URL) would it?

Any thoughts would be greatly appreciated!

Obviously you would need to have the domain hosted somewhere in order to have its traffic redirect. However, it is possible that your DNS provider offers a service such as URL redirect or URL frame, which would send all traffic going to olddomain.com/whatever to newdomain.com/whatever. This service varied by the DNS service/registrar, so if you wish to do it this way, it may or not be possible with your setup. Who are you using?