So how about current CPUs? Modern CPUs are vastly bigger and more complicated than a 6502, and they are also set up very differently. So simulation is not taking us anywhere, but we can fuzz.
Sandsifter is such a CPU fuzzer: it generates every conceivable instruction byte combination and then tries to observe what happens.
Sandsifter has uncovered secret processor instructions from every major vendor; ubiquitous software bugs in disassemblers, assemblers, and emulators; flaws in enterprise hypervisors; and both benign and security-critical hardware bugs in x86 chips.
The findings have been summarized in a whitepaper (PDF), which also describes how to effectively search the instruction space of a CPU that has variable length instructions from 1 to 15 bytes in length. A crafty way of using page faults to determine the length of privileged instructions while running unprivileges is shown.
The strategy implemented reduces the search space from some 10E36 instructions down to about 100 million, which is a manageable size on modern CPUs. Known instructions (things that some reference disassembler knows and correctly predicts) are eliminated, the rest is interesting and deserves attention.