When doing that digitally, your codec decides if that is even feasible. If the codec optimizes for disk space, generating any frame requires going through all previous frames. If the codec optimizes for fast scrubbing, the file must contain redundant information and thus be larger.
Nokia is claiming that h264's checkpointing mechanisms allow for that (empirically, this is indeed a feature of h264) and it is therefore their invention. I'm unaware if previous codecs had similar mechanisms. It would be wierd of none had, but it wouldn't surprise me that much.
No it doesn't; that would be crazy. There are keyframes that can be decoded independently of any other frame. They're usually every few seconds at most, which is fine for scrubbing.
...But video players have had scrubbing bars for a long time? I'm not sure how long, my memory on Windows on XP and older is fuzzy.
Meanwhile e.g. Apple has very strongly enforced similarly silly UX patents. (E.g. rubberband/inertial scrolling and quite a few more.)
They have also very strongly enforced silly design patents - e.g. for rounded corners on physical devices.