Zero said:

Since all of these deleted scenes are presented in high-definition 1080p video, it is possible to edit these scenes back into their respective movies.

Very nice cleanup you did, but I'm sorry to say that the particular video you're cleaning up is actually upscaled from DVD.

I suspected it when I watched it, so I did a test: Grabbed some frames, downscaled them to 720x480 and upscaled them back. They look identical except for some added sharpening, which was maybe done to disguise the fact that the clip wasn't presented in it's full resolution.

http://img829.imageshack.us/img829/8458/01original.png
http://img819.imageshack.us/img819/7070/01resized.png
http://img838.imageshack.us/img838/9613/02original.png
http://img542.imageshack.us/img542/9718/02resized.png

Considering this, maybe it's better to downscale the whole video before cleaning it up?