I opened up a console and
cded into my desktop,
dired the folder contents and started removing files one at a time (starting from scrap files I could most easily replace, obviously), trying to launch Explorer after every try.
Here's a condensed output from my console
27/12/2011 17:18 <DIR> .
27/12/2011 17:18 <DIR> ..
16/12/2011 22:05 <DIR> Cobalt
17/12/2011 22:16 <DIR> CS
09/03/2011 22:58 <DIR> DD
11/12/2011 12:18 64.136 dingaling.wav
01/06/2011 21:36 <DIR> Dolphin
23/11/2011 07:34 <DIR> Erasmus
26/12/2011 23:51 11.805.121 familyfeud-playaround-heisanevigenius.mkv
04/06/2011 20:28 <DIR> foo
<!--------------------------------- snipped a few more files --->
After I deleted this .mkv file, explorer stopped crashing. I wanted to make sure it was just this mkv file, so I redownloaded it. Sure enough, it crashed again. Rebooting didn't help.
As Tom suggested I used ShellExView and noticed only one item of type "Thumbnail" that wasn't provided from MIcrosoft and was about videos - "DivX Thumbnail Provider". It sounds unrelated (after all, DivX and MKV are different things) except the description claims "DivX MKV/AVI Thumbnail Provider" and disabling it fixed the problem.
Should I want thumbnails back for .mkv files, I could just reinstall/repair DivX again. Honestly, .mkv files play just fine and those thumbnails were fairly expensive to make anyway, so I'll happily live without them.
As for how this happened just by randomly clicking on the desktop... I have honestly no clue. The issue had likely happened in the past and the right clicking simply triggered a rebuild of the cached thumbnail, which crashed.