I'm away for the weekend and so will not be able to follow up with more detailed information for a few days: But remember that my primary aim here is simplicity, something that is easy for other people to build. For that reason, I am aiming to use no hardware other than the Arduino itself if possible.
There is one headache that I've just thought of - the aim was to use the Arduino's serial USB port for communication with the host PC (so I could send an intel hex file to it with, eg, Hyperterminal). However, the USB connection also provides a hardwired 5V supply to the Arduino, which is awkward as I want it to be powered from the target system, for the reason previously discussed. The target system certainly can not draw its power from the USB connection via the Arduino - it takes well in excess of half an amp.
I actually can't remember if the act of pressing a key stops the scanning action or not - I'll look into it. Certainly on the prototype (using optocouplers) the target system's debounce delay is what ultimately limits the maximum typing speed of the interface - it has to press each key for just long enough for the target system to always accept it as a valid keypress. Nonetheless, it is still surprisingly fast. If you want to see the optocoupler prototype in action, here's a youtube video of it working. Scroll through to about 1:58 to get to the interesting bit.
If you are wondering where the optocouplers are, look carefully at the programming interface which is built on stripboard. It's actually a sandwich of two identical-sized pieces of stripboard mounted one above the other. The PIC processor and MAX RS232 level shifter and an 8K serial SRAM are mounted on the top board: The optocoupler matrix occupies the entire lower board.