Vuclip (which used to be called Blueapple.mobi), is a video search engine. It searches and indexes over 150 million videos from sites like YouTube, MetaCafe and Versaly. I was able to find videos for almost every query I tried including music videos, TV shows and sports.
Vuclip uses browser detection to deliver files are optimized for almost any video capable phone. Formats range from low bandwidth 176x144, H263, AMR, 3gp, split into 500KB, 1 minute segments for low end devices to high quality, 320x240 5 MB .mov files for the iPhone.