The Myth series made by Bungie had a neat way of doing the replay thing which might work for CM.
Basically it only saved the math, eg where each unit was, when it hit, what damage it did. When it came to the replay it'd simply redo the math, you couldnt fastforward or rewind the movie. It'd use the game engine to reload the map and graphics, so if you didnt have the game or the 3rd party map the battle was fought on you couldnt watch the movie.
Hope that makes sense, i'm sure CM could use a similar system.