It's worse than that, as the algorithms are not simply parallelisable (frames relate to each other). Of course you could chop the film into 100 pieces, and compress each individually, but you would lose some compression rate which would (partly) defeat the whole purpose.
Not really - the encoder tends to reset quite often, e.g. it is recommended to insert an "I" frame every 5 seconds or less (stands for "intra coded", but could be thought of as "independent") - so that you have to decode at most 5 unused seconds when doing a random seek.
