Emulator

Mario Kart Wii ghost cars have the same problem. Probably related?

Interestingly, this only happens with staff ghosts. Haven't tried it with any player-created replays from the real console, but I bet this is because Dolphin is an imperfect emulator. An imperfect emulator creates a ghost, the same emulator plays back the ghost it created properly.

After a bit of testing, I was able to get replays to sync 100% consistently by enabling the DSP LLE Recompiler audio engine. This is regardless of Dual Core, Idle Skipping, or video backend settings.

tl;dr HLE audio breaks things; this bug is dubious.

Are you talking about replays from the Wii, or replays from Dolphin?

If this is true, then there's an issue with HLE... which is something I honestly didn't think to check for replays.

I just double checked Mario Kart Wii/Double Dash, just to make sure, and they are not fixed by using LLE.

I also can get my Brawl replays recorded on Dolphin to record/play fine on HLE as long as they are recorded in Dolphin.

The Wii replays are another story with Brawl; I don't have any from my Wii to check right now unfortunately.

I was talking about replays originating from a Wii being played back on Dolphin.

Well, I spoke too soon anyway. Changing the audio to LLE fixed 1 replay 100%, but the 2 others I tried didn't change at all.

Wow, I need to be more specific.
I was talking about RSBE01 (SSBB US version). A replay of Ice Climbers vs. Marth was fixed by LLE, but none of IC vs. G&W, IC vs. Olimar, Marth & Zelda vs. Marth and Samus, or Marth & Zelda vs. G&W & Falco were fixed. So that's only 1/5.

Also, The replays were recorded on the Wii using CFG USB Loader's cheat engine with the No Random Tripping code. I created an SD Card for Dolphin with the same GCT, then loaded GeckoOS.elf each time I wanted to view the replays. It seems to be working fine, and I don't think it's causing the glitch. From my limited testing of Dolphin's own cheat engine, the results are the same.

I have tested a lot of SSBB 1v1 replays recorded in Wii.
And found that using "JITIL experimental recompiler" could prevent most replays from desync.
BUT some of them (especially replays with Olimar) still doesn't playback correctly.

Maybe, the biggest reason of desync with JITIL is random tripping.
Just for your information, when I chose "JTL recompiler", most of random trips were emulated correctly.
Of course compared with JITIL, JTL causes a lot of desync from item, edge, etc... but EXCEPT tripping.
I hope this may help you.

Please try this build if you're still around: https://dl.dropboxusercontent.com/u/484730/DolphinMoreFPWork.7z

I've tested your build, but the problem has not been solved yet.
(I attached the replays I used in my test.)

Game1(Olimar vs Wario in Final Destination):
around 7:35, Olimar tripped in Wii, but he didn't in Dolphin.
Game2(Olimar vs Zero Suite Samus in FD):
this replay play back correctly, thanks!
Game3(Olimar vs ZSS in Battle Field):
this replay does not play back correctly, but I cannot detect the exact start point of desync.

The accuracy of Replay was slightly improved, but not yet complete.
I know this problem is not so serious in playing the game, but I'll be really glad if it is solved, thank you for your time.

I didn't expect this build to completely solve it, but it should make it so that JITIL and JIT desync the same way, rather than JIT desyncing more.

I see.
Then, exactly as you say, there was no difference between the operation of JITIL and JIT.

Okay. So magumagu fixed the extra JIT bugs that were causing replays to not synchronize. Now comes the hard part of finding what's broken causing the rest of the desyncs.

I was messing with this and... well... I dumped 85 replays from my Wii from when I played Brawl competitively. I played a random assortment of 20 of them. While sometimes I thought it desynced from how bad I played (2008!) all of them worked.

I tripped like 15 times in one of the rounds, and that one didn't desync, so...?

Also, no one I knew played olimar, so, I had no replays of olimar. Could be that all the desyncs are centered around him.

That's true.
Almost all desyncs I confirmed were caused by Olimar.

Can you please try: https://dl.dolphin-emu.org/prs/pr-834-dolphin-latest-x64.7z

This could be what finally fixes this in the JIT. I was unable to reproduce any desyncs with this build.

I tested some replays with Olimar, and confirmed that there are no desyncs anymore!
Really thanks for the fix, and this is very delightful for everyone in the Smash Community!