Maybe you could index key parts of the frame and use that to narrow it down bit by bit (pun probably intended)? So confused...
You chunk a song into small segments and create a sort of "fingerprint" for each piece using Fourier analysis or similar. (So a song segment is represented by a frequency histogram, similar to this: http://www.flickr.com/photos/svartling/4229109164/ ) The fingerprints are stored in a DB.
To match a song fragment, chunk and analyze it in the same way. For each segment, find the closest match in the database. If most of the closest matches belong to the same song, and appear in the same order as in the song fragment you are trying to find, you have a match.
Creating fingerprints from a series of video segments is roughly similar, Fourier can be used for 2D images as well.
Doing it like this, you can reduce the volume of data you need to compare against with several orders of magnitude. Scaling to YouTube volumes is still hard, but that's the sort of scaling a company like Google already has plenty of experience in.
- make the chunks small enough that they are essentially static images (one or a few frames)
- use some form of dynamic chunking where a chunk lasts until the image is sufficiently different according to some metric.
In both cases the chunks are fairly resistent to changes in speed, and the worst you need to deal with is that multiple chunks in clip A may map to the same chunk in clip B.