But fast forward is usually almost instantaneous, to the point it's often faster to seek backwards, then play back at normal speed, than to wait for a previous frame to be calculated.
There's no reason why the software can't cache frames (it's only 25fps normally) or fast forward from the last I-frame. 25 frames of 1080p HD video is 200MB, as uncompressed 32bpp bitmaps. I have 24GB of memory in my PC; that's the worst case, and it's not bad. A bunch of prior frames can be cached, and the next bunch recalculated if it looks like the user is going to continue stepping backwards.