REDIRECTING FROM AN OLD SITE

Hi, People

We have a website from another host, say

http://www.MyOldSite.com

and I wanna redirect people to my new site:

http://www.MyNewSiteAtDiscountASP.com

Displaying a page telling people that we
have transferred and that they should update
their links, blah.. blah.. blah...

However, I wanna get rid of my old Web Host.
I don't wanna keep any files from my them,
otherwise I would have to pay them every month
for that single file that displays the message
and does the redirection.

Please note, that I need to display the message
which will be stored in my new Web Host, not just
simply redirect it to the new website.

Any ideas?

Thanks

MSolve1