Making a rerecording PC emulator is possible. But it is hard. First of all, most popular PC emulators use various speed tricks which involve passing instructions through to the underlying machine, or using its interrupts etc. This breaks the encapsulation of the emulated machine, and makes it nondeterministic. Not all PC emulators do this, though, and for those that do, it should be possible to rewrite those parts (a huge project, though smaller for somebody already deeply familiar with that emulator).
Secondly, a PC has lots of different parts: Network interfaces, com ports, sound cards, graphics cards, various buses and bridghes on the mainboard, etc. etc. Even if the emulator actually emulates these, instead of using those of the underlying system, saving the state of all of these correctly is difficult unless the emulator was designed with savestates in mind from the bottom up. And incomplete savestates lead to desyncs, just like nondeterministic emulation does.
Thirdly, the state of a PC is larger than that of a typical console. By a factor of a million or so. This means that, unless differential savestates are implemented, each savestate will take up gigabytes, and take significant time read and write. Which would make tasing irritating. On the positive side: If differential savestates are implemented, the step to non-linear rerecording, with a branching tree of savestates you can jump between, is pretty short.
Fourthly: The concept of roms is more complicated here, but as discussed in a (relatively) recent thread, it is still possible to reach a setup that will allow movies to sync without having to distribute the whole state of the VM (which would contain copyrighted software). However, the presence of license keys etc. prevents this from working, so this could only legally be done with license-key-less software.
Fifthly: The movie would have to contain a set of inputs for every device on the emulated PC which could accept input from the outside, for example the network card, mic, mouse, keyboard, power button, dvd eject key, etc. This isn't a big problem, though.
That said, I would also like to see such an emulator. I recall speaking to somebody who was making a rerecording version of JPC, which he said was already deterministic (which is the greatest hurdle in my opinion). I haven't heard anything since then, though.
Do any of you know of any other rerecording PC emulator projects?