I've recently had some though about the subject of simply recording a movie file for a PC emulator. Bochs might be a worthy choice, as it's a true PC emulator; slow as it might be to run, it doesn't take any hacks that might jeopardize accuracy and the correct playback of movies. Qemu might also be considered, but it is a dynamic translator (uses a hack that translates emulated binary into native binary; often at the cost of accuracy), so it might not truly be the ideal choice.
Now unless you're TASing software you are allowed to distribute legally, transfering disk-images will be illegal. This isn't entirely a show-stopper; you can attempt to make a movie file of the system installation process. For example, provide movie files that cover the installation of Windows 95 and Starcraft (if that's what you were doing). If the movie record/playback were carefully designed, it should work flawless if the same installation media are used. In terms of proprietary software, "same installation media" could very well be the worst step; there's hidden revisions everywhere, it could throw someone off unknowingly. Not to mention the fact that many people might have lost the original medium of a piece of software, and the backup they have is of only the files; for example, if you have a remastered Windows 95 disc, it should be identical enough that the movie file does not break (the possibility of this is uncertain; all sorts of things happen in PCs not normally known; next paragraph).
In order to make the movie files play back flawlessly, much more care will have to be taken than console emulators are. For starters, a PC has dozens of different points input can be taken (versus consoles usually having a few buttons). Input can happen from the keyboard, mouse, serial, parallel, modem, ethernet, APIC, APM, USB, Firewire, and much more I did not mention. Normally this would make a very large movie file if recording everything; however the movie format should be made flexible where hardware components can be left out if not enabled in the environment. Still a large file is to be expected for a minimalist PC configuration; using gzip compression could potentially reduce the size drastically for transfering images. Not to mention all the various components might have to be manipulated to the fullest if a program relies on input to generate random data (for example, the Linux and *BSD /dev/random node); if you think manipulating Pokémon Red is difficult with eight buttons, try manipulating a PC step-by-step (equivalent to "frame advance" on the console emulators, but not the same since PC internals are not in sync with video output) with all the various components of varying bandwidths (keyboards come anywhere from 90 to 120+ keys; PS/2 mice have two 7-bit axis; I don't know how much goes through the serial and parallel ports and other such stuff, but it's going to be a lot). While this sounds daunting and everything, I'm sure there are going to be some people willing to make a PC-based TAS if it were possible.
(O yeah, last thought: You'll also have to store some CMOS and BIOS settings (eg, date/time) in the movie file. Not sure where this goes in the paragraphs, but it's important nonetheless.)
Naw, it's not impossible by a long shot. Actually implementing movie support (and even re-record) should be the easiest part, using the feature will be the most time-consuming part.