As a Video DSP Engineer, I can attest that it is definitely possible and practical to register motion of a fraction of a pixel. I've used such a technique myself (and this general notion is far from new, though its use to extract sound may indeed be).
Consider an image of a coin, say, 80 pixels wide; if it moves as a whole by, say, 1/10 pixel, there will be tiny but well coordinated changes in most of its hundreds of pixels, which can be mathematically analyzed; in fact, given a single frame from the video, you can analyze it and predict that if the coin moves, say 0.04 pixel to the left, then a particular pixel will get brighter (or dimmer) by a certain amount. Any individual prediction may not be accurate when compared to actual motion, but averaged over hundreds of pixels, you can get very good results, especially in ideal conditions (still camera, uniform lighting; good focus...). So you then mathematically work back by comparing the predictions to the actual changes, to estimate the motion.
This technique http://en.wikipedia.org/wiki/Optical_flow is one which can be used, and is similar in its approach to what I've described; here is another: http://en.wikipedia.org/wiki/Phase_correlation
A more difficult limitation is that you have onlr whatever number of audio 'samples' per second, depending on the frame rate. For conventional video, this number is typically in range 24 ... 60, which is too low to resolve interesting audio. The music samples on the web page http://people.csail.mit.edu/mrub/VisualMic/ are all very low notes; however a sample rate of 2200 Hz is given. For applications where you want to understand speech, you'd want to have at least 1000-2000 samples per second, and up to 4000 or 8000 if you want to be able to identify the speaker by the sound of their voice. Refer to this http://en.wikipedia.org/wiki/Voice_frequency -- but be aware that standard telephone processing uses 8kHz sampling, and is clearly more than adequate for clear speech of even higher-pitched voices with ability to recognize the speaker; lower sample rates can still yield intelligible speech.
The paper also discusses taking advantage of the 'rolling shutter' effect in a video camera to get more continuous audio information.