Are these programmes in the realms of stretching the truth a bit
By quite a margin

or can it be done, but costs the earth?
If the image has the information already there the information can be extracted but the idea of a computer system which can create non existent information from a few clues isn't quite with us yet.
Most (if not all) professional photographers who use digital imaging do so using RAW files at the highest settings available and wouldn't touch jpeg's with the proverbial bargepole .....
Many digital CCTV systems are capable of capturing images at much higher resolutions than ordinary video and again if the required information is there a suitably high powered computer system could zoom in without as much pixellation as normally seen but I believe a lot of "artistic license" is used in those shows