I know there are some people that are happy with the results of using variable timesteps for various reasons, but I would never recommend them for anything other than physics for purely graphical effect purposes. Instead I would definitely recommend decoupling your update and drawing loops. Always run your game logic code at a fixed rate, and render as often as you can push to the screen. It solves a lot of problems, and is a great article on how to do it: http://gafferongames.com/game-physics/fix-your-timestep/
I guess the need to playback code that is triggered from collision events without running the physics throws a bit of a wrench into things. If you are always replaying the simulation from the very beginning, then it's possible without a lot of extra work. As long as you initialize the physics in the exact same way and modify the physics in the same order on the same frames, you should be able to get an exact replication of the simulation by only recording the user input. The only catch is that you need to call cpResetShapeIdCounter() (http://chipmunk-physics.net/release/ChipmunkLatest-Docs/#cpShape-Misc) and be careful with any random numbers you use.
However, it won't work between different CPUs/OSes/compilers/versions, etc. Even changing compiler flags mean that some floating point operations will possibly get reordered and cause slightly different rounding errors. A round off error of 0.000000000000000001 pixels might not seem like a big deal, but after hundreds of frames and hundreds of objects interacting, that could end up being a whole pixel. That 1 pixel change might be all you need to bump into something you weren't supposed to and greatly change the outcome.
Anyway. I guess if I was doing it I would always run the replay to start from the beginning and just play back the user input. It's pretty easy to make a game record just the input, easy to make it play it back, and uses a trivial amount of memory. If I wanted the replays to work between CPUs/OSes/compilers/versions I would make the game record the position of everything in the game as well as things like events triggered from collisions so that they could be played back to spawn explosions, remove objects, etc. It's more work to do this, but I really don't think you have any other choice. Even if you do this you have to be very careful that later changes to the game (changing the amount of damage a monster does) don't break the replays, or also record all of that information too. I would seriously avoid doing this, it seems like it would be a waste of time.