Host your videos on Google!
*** UPDATE 8/9/2005 - Google launched this service about a month ago and I've been serving videos since. It's VERY cool, but requires you to download a browser plugin. Google is about to launch a new Video service. From what I gather, it will do two things.