Emulator

Try using the latest SVN version. Also using the LLE recompiler audio option might fix the crash too.

If neither of the above fixes it, let us know if disabling Dual Core mode works.

Still using r6987
Disabled "Use Dual Core" and "Lock Threads to Cores" options. (they were enabled when I first tested)
It seems the error wasn't as predictable as I said, now I load a state and I can go on loading it and it won't fail, but if I save both in menu and in game, it crashed sometimes and sometimes it doesn't, unpredictably.
Test 1:
Start Dolphin, load game, load state, reload same state, crashes. Close game (dolphin doesn't crash - only game). Close dolphin.
Test 2:
Start Dolphin, load game, load state, reload same state, crashes. Close game, close dolphin.

By game crash I mean: it doesn't respond to input, the screen isn't redraw (but doesn't go blank either, stays the same), and the game window title stays the same (fps doesn't change, etc).

Activating LLE recompiler audio: game doesn't even start now. I get several error message boxes and the both the game and dolphin crash.
Errors:
"Failed to load DSP Rom: ./User/GC//dps_rom.bin"
"Failed to load DSP Rom: ./User/GC//dps_coef.bin"
And then something about dps_rom.bin having incorrect hash.

r7093 still fails, tried using different options (in particular, disabling audio output and most graphics options).
Even wrose, I tried just loading the Slot 2 state by pressing F2, and it fails randomly (works maybe 10 times then crashes, restart, works 5 then crashes...) without doing anything else.

Shouldn't the test be Start Dolphin, load game, save state, reload same state?

Also, if you install a new revision of Dolphin, the old state might not be compatible so a new save state has to be created.

The state was new with the new version.

The tests were many (probably I just tested it 100 times), I only wrote here the ones I thought were most important, but just as examples. I can't possibly write every single test I make and I haven't really found a pattern myself, I really combined all I could think of, until I came to the simplest case: just repeatedly loading the same state, and even that fails randomly. I tried loading too many times too fast, faster than it can load, and it worked some times (hanging for a second and then displaying 4 "loaded state" messages), and failed others.
By the way it's both loading and saving that fail at random: it sometimes crashes on loading a state, sometimes on saving it.
Tried different slots too, but most tests were made on slot 2.
Tried with and without dual core, and with and without lock threads to cores.
With and without sound options.
With and without video options.
With DX9, DX11, and OpenGL. (yeah, lame, I can get pretty desperate when searching for a bug...)
Now that I think of it I even tried using both the USB controller and the keyboard (but it wasn't intentional)

And... now it seems to work perfecly, and I have no idea what changed. Gosh I hate this. Anyways its late, but I'll go on updating this post as I play this game.