This is really nice. I wonder if anyone has tried fuzzing a CPU's instruction decoder? It would be surprising if they didn't have bugs.

Yep! sandsifter[1] does exactly that.