IMO Spelunky seems like one of those cases where it would be easier to add saves. You can't go backwards so you "only" need to save the seed, player state, and the state of enemies/items/etc. in the current room. I really don't get how the randomized nature makes it harder - the seed should contain all the data you need to regenerate everything - since that's how it was created the first time. Regenerate the level - apply the state* - and you are right back where the player saved.

I'm a developer (but not a game developer) so I know things aren't that easy, if your original world generation wasn't built for this you are probably screwed. Maybe I'm way off base here though so if someone else could chime in on the difficulty of saving worlds generated by seeds - that would be great.