Joe, Re: Instruction extention - yes, microcode edit - no.
If you have a 64-bit ALU, you can change the microcode to make the instruction format whatever you want. Intel had a 64-bit ALU built into Prescott. Whether it was compatible with x86-64 from the beginning, we'll probably never know, but all it takes is a tweak of the microcode to make any set of instructions work on it.