I imagine building a table of, say, 100 IP values that are only ever visited in order. That is, IP table 5 will never be seen after IP table 6 has been seen. But even that isn't necessary. You could just say, "the first time I see this IP value, increment to 37%", so that the progress bar never moves backward.
The progress-bar-as-rewind idea is very cool, too.
Nah, you are overthinking it.
You can record how many frames or cycles it takes for the first thing to appear on the screen.
Since the emulator is deterministic and you are always starting from the same state, it will always take the exact same amount of emulated time (for each version of the emulator). So your progress bar is simply a measure of emulated time.
Or take it a step further, and store a savestate from the moment the first thing appears on the screen, and the user's emulation will start from there instead.
Also, I have secret plans to use the progress-bar metaphor as an interface for accessing past game states. Imagine if you started playing Pacman, and the progress bar started filling up. Then you click in the middle of the filled-in bar to jump back to that place in time...