Emulator

Game Name?

The Legend of Zelda: Majora's Mask (PAL)
The Legend of Zelda: Ocarina of Time
Super Smash Bros. (PAL)
Pokemon Puzzle League
Super Mario 64
Likely others

I'm not at my main box to put the GameIDs, sorry.

What's the problem? Describe what went wrong.

These games tend to run incredibly erratically regardless of settings. Each game has its own weird problems that manage to crop up.

The Legend of Zelda: Majora's Mask (PAL only) - the game runs incredibly fast and with a huge frameskip per frame. Audio also does not play. Unrelated, the game crashes trying to write a savefile on J/PAL. NTSC crashes even earlier.
The Legend of Zelda: Ocarina of Time (All regions) randomly hangs. It's incredibly common, letting the intro loop will bring it very fast.
Super Smash Bros. VC (PAL only) runs incredibly fast depending on scene. The more stuff on the scene, the more it runs closer to console. Can hit hundreds of frames per second in the main menu.
Pokemon Puzzle League has the timer run far too fast.
Super Mario 64 - The "Classic Controller" screen instantly fades away.

What steps will reproduce the problem?

Run any of the above games.

Which versions of Dolphin did you test on? Does using an older version of Dolphin solve your issue? If yes, which versions of Dolphin used to work?

This happens regardless of specifications or version of Dolphin.

Is there any other relevant information? (e.g. logs, screenshots,
configuration files)

I actually discovered a partial solution to this that is probably 100% incorrect, but may be leading us down the right path to actually solving the problem. By setting the following settings,

SyncGpuMaxDistance 100
SyncGpuMinDistance -100

and using SyncGPU, you can actually get the games to run mostly correctly! The timings aren't 100% perfect in Super Smash Bros. VC, but they disappear altogether in the other titles. You can actually get them even closer by using the GPU Clock feature that degasus added in the rewrite, but, I haven't found the perfect settings yet. This points toward some kind of GPU synchronization issue; namely, Dolphin emulates an infinitely fast GPU. I believe these games rely on a GPU that ISN't infinitely fast! The problem with my solution is that it makes these N64 titles outright impossible to run at full speed (outside of Pokemon Puzzle League, which eeks out at 30/60 just barely) If we could properly implement this in Single Core, it would probably be a lot faster. Or heck, maybe properly emulate this at all in any kind of setup.