Great article! Chris Rohlf and myself gave a talk on attacking JIT engines at BlackHat earlier this year[1]. We covered JIT sprays and mitigating against them fairly thoroughly (not this thoroughly, but our goals were a bit different :)).
The short story: arbitrary computation by finding 'ret's wit short sequences of useful code before them. Finding them in your code, and they need not actually be 'ret's thanks for the same reason this stuff works.
Or runtime environments that enforce some of these constraints on binaries for variable-length-instruction architectures [1] :)
Variable-length instructions, when done right, closely approximate Huffman coding your binary, so you can get big code size wins, but there are definitely hardware/system software complexity and security disadvantages to be aware of. An intermediate point between, say, MIPS and x86, is something like ARM's Thumb, where you have one set of small instructions for your most common operations, and you can distinguish between the two in hardware without much hassle.
Agreed -- you can get large code size wins. This would require actively managing the instruction set so that the most common instructions are shortest. In theory, this could be done.
However, this doesn't work for a legacy architecture like x86, because many of the short opcodes are no longer the commonly used ones. Some are even actively deprecated. So overall, ARM wins in code size. I'm not sure about x86/64, maybe it is better there...
Check it out if you're into this.
[1] http://www.matasano.com/research/jit/