As far as i know its a bit of both of the above. Avi's and certain mpeg formats have "key frames" embedded every so often in the stream, usually at regular intervals. The higher the number of key frames the more discrete jumps you can make (eg 1 second jumps for a pal movie with key frames every 25 frames). I would assume if there are no key frames then you could not scan the stream at all.
Also the player makes a difference, as they use different methods of resolving codecs at a software level. You may notice that you cannot fast forward or reverse a divx in eg WMP, but in a proprietry divx player you might be able to).
There are ways of changing mpegs and avis to scan more easily but they usually involve a degree of re-encoding which may or may not be worth the hassle!