Good news and bad news.
Good news: I found a sort of a "corner boost" trick that can be used to maintain the running speed while falling. Normally, jumping and falling can only be done in walking speed, but by swinging the sword at a correct frame when running off an edge of a ledge, the character keeps horizontal running speed while falling. It is not an obvious trick, because using the attack button in any other situation will slow down the speed. (On the other hand, corners are always special cases, so I should have found the trick earlier...)
Bad news: I had done 40 minutes and about 40 000 rerecords, before I learned the trick. Using it consistently would save about 20-30 seconds up to the point where the WIP ends. I don't know what to do with the WIP now. Continuing it seems pointless, but restarting the whole movie feels uncomfortable too.
Anyway, I'm happy that I found the trick and many other tricks during the process. I knew that something like this was likely to happen. I feel discouraged now, but maybe I'll restart the whole thing someday, especially, if somebody is willing to join the party. So, if you are looking for a good game to TAS, please take a serious look at this game. I have many useful RAM addresses, savestates and other knowledge about the game, so I will be here to contribute as much as I can, possibly recording some major parts for the next run too.
Surprisingly, this game is hex-edit friendly to some extent, because there are lots of things that are reseted when a screen is loaded. This fact might make it a really funny project to work on with somebody.
Here is the movie so far:
http://dehacked.2y.net/microstorage.php/info/408853094/MW4-WIP.gmv
I think the WIP looks very good already.