Finally after spending too much time on it, it's done. I wound up implementing both forwards and backwards stepping, and simplified things in the process. Previously I had a stream of MIDI messages and would step along them by finding the step position, calculating the next step, finding the resultant RealTime, and playing that many MIDI messages.
I changed it to produce all the step points along with the MIDI state at each point, right off the bat, and store that. Then stepping is just moving forward one state, diffing it with the previous one to generate a set of MIDI messages, and playing those. Now backwards is as easy as forwards. And the StepState is much simplified, and the stepping functions don't have to know anything about the steps or about RealTime, or anything like that.
In a strict language, this approach wouldn't work because it would immediately want to realize the entire score just to play a single note. Sometimes I'm on the fence about whether laziness is worth it in the long run, but this is another point for laziness.
I'm still not sure whether backwards scrubbing is really worth all that craziness, but it's kind of fun to mess around with.