My theory: If I have a 100x100 pixel movie - and it has lots of noise - I can resize it to 25x25, and remove noise at the same time. This is because 16 source pixels = 1 pixel on the final cut, and this 1 pixel is an average of the 16 noisy ones. Therefore a much better signal.

Am I correct? I have DV footage (shot in frame mode) that looks noisy, and I don't mind reducing the size of the movie to enhance it.

Yet simply changing the output resolution in premiere doesn't seem to cut it.

Your theory is sound in theory. However it largely depends on
how the downsample is done. See if you can change the way
Premiere does the downsample. It might just drop columns and
lines instead of averaging them out.

If straight downsampling is performed, not only there will be no noise reduction, but also extra aliasing effects will be introduced if the original (yr 100x100) was sampled at near Nyquist limit. Most decimators used for downsampling use FIR or IIR lowpass filtering before downsampling. Whether noise will be significantly reduced if further dependend on the original noise "spectrum"