The suggestion isn't to implement, say, Vector Add in an illegal instruction handler; instead, it's to use the illegal instruction handler to replace the Vector Add instruction with a jump to a user-space emulation routine. The emulation routine may /also/ be too slow to be usable, but the trap overhead is a once-through cost, not a per-execution cost.
Doable, but you end up having to generate a unique sequence for every single instruction in the program because for something like 'mul r1,r2,r3' your going to have to move the information about which registers are being multiplied somewhere else, as well as encode the return address, and as you mentioned the register spill/etc is going to be costly or you have to reserve a couple registers for it.
There are a lot of problems doing it that way too, particularly if your on a small microcontroller with limited ram.
