Yet both noise-reduction and resolution-enhancement are both fundamentally about taking whatever information you do have and using that to interpolate/infer information that has been lost (or was never captured).

Especially in certain domains such as written letters (e.g. license plates) or faces that have a well-known structure with variations in known dimensions, I wouldn't be surprised to see algorithms that can probabilistically infer what information would have originally been there. Of course you'd never reconstruct an entire face from a single pixel, but how far can we go? I dunno - but my hunch is pretty far