What is this noisy shadow overlay that stays with the camera?
That looks to me like "regular noise" (I assume by regular noise you mean noise caused by an insufficient number of samples in cycles). 

By default cycles uses a consistent pattern for sampling, and so the pattern of noise will stay the same, producing an effect like this:



On the dark side the noise is more chaotic, but on the illuminated side of Suzanne's face you should see that the noise pattern remains mostly the same across frames.

To fix this, change the Seed of the noise pattern so that it's different every frame (or every few frames), and/or increase then number of samples. To do this, type #frame into the Seed setting in Render settings > Sampling:



This will create a driver which will set the Seed based on the expression typed into the field, where #frame is equal to the frame number.

Note that you may have to allow the driver and reload your .blend (save before reloading!) in order for the driver to work. See After updating to Blender 2.68 Driver Scripts are no longer automatically excecuted for details.

Optionally add some math to the expression, e.g. #frame/10 to change the seed only on every tenth frame.

This will break up this noise and make all the noise chaotic, which makes the noise less likely to be preserved by lossily compressed video formats.



Click the image above to see a compressed video version.

On more recent versions of blender there is a button to change the Seed automatically:



The small clock icon highlighted in yellow here, when pressed will automatically adjust the seed each frame.