I recommend reading this discussion about a new format for Genesis movies:
http://tasvideos.org/forum/viewtopic.php?t=3995
... and the specifications we have worked out during it:
http://tasvideos.org/GM2.html
It includes some of your ideas: subtitles, savestates for rewinding, extensibility.
Some other comments:
>The format shall be formally documented in the hopes that various emulators would add support for it.
See
http://tasvideos.org/FAQ.html#emulators_ -- all the movie formats are reasonably well documented.
>Controller data would be encoded as delta-time.
FCM does this and everyone hates it, because it's practically impossible to hex edit the movie files. The movies are rather small anyway, and compress very well. Emulators can read ROMs in zip files, so there's no reason why they shouldn't be able to read movies in zip files.
>Rather than encode the state of the controllers at each frame, I propose that instead the format record the state of the controllers at each read probe.
This sounds like a good idea in theory at least. M64 (Mupen movie file) does this but has still had a fair share of desynch problems, but perhaps they are unrelated.