QEMU is far from deterministic enough, and making it so seems very difficult. On the other hand, I spoke to somebody in #tasvideos who was almost done making a deterministic (and hopefully rerecording-enabled) version of JPC, which is another PC emulator. So getting this is perhaps not too far fetched.
There is no reason for there to be any cans of worms involved either, no matter whose worms those would be. The way to do this is just like how we handle sram now: When a movie needs to start from sram, one has to provide a movie that generates said sram, right? Here is how a TAS of some windows game would work:
Instead of one having a rom of the game (which would be a can of worms, as you say), runs of the game would start from a standardized savestate. This savestate would be one where windows and the game itself + dependencies have been installed, and the game exectuable just started. This would serve as a common starting point for all runs of the game.
This savestate would ofcourse not be distributed, since that would, again, be a can of worms. What would instead be distributed is an emulator movie which generates this savestate. This movie would start from another savestate (the "windows just installed" savestate), and would contain input like "eject CD tray", "insert CD with hash 5bba729dcfe9", "close tray", "move mouse to X,Y", "click right button", etc. etc., which would lead to the game being installed and configured.
The savestate the "install game"-movie started from, which is the "windows just installed"-savestate, would be generated in much the same way, but this one would start from a standardized plain state (downloadable from tasvideos, and without anything installed), and not from another savestate.
So each user would have to make sure they have the correct CDs, and would then have to play back the "install windows" and "install game" movies once in order to generate the standard savestate from which tases of the game would start. And since nothing but input is distributed, there can be no problems with this.
The only conceptually new thing needed for this is an emulator movie instruction to insert a specific CD on a given frame.
Just like the ROMs are checksummed to make sure the right one is being used when playing back a movie, so would the starting savestate be. In fact, the starting savestate plays almost exactly the same role as the rom, does now, except that one has to generate it oneself (by playing back a movie).