If finding neutral is a problem, you could have a small, secondary solenoid that places a bar in the way of the shifter, so that it gets stuck at neutral the next time you shift. Have it set up so you hold the "Neutral button" and shift with the normal button.
I like it!
Though I think the mechanical linkage or cable is the way to go, bikes shift better when you preload the shift drum before going for the shift, and a solenoid can't really do that.
I haven't put the Megasquirt on my car yet but I've programed it and a PIC to read what gear the transmission is in and when you move the paddle shifter to upshift (which will basically energize an electrical circuit when the mechanical pressure has built up on the cable) the PIC will start the shift sequence by commanding the Megasquirt to cut the fuel off. When the PIC determines the xmission is in the next higher gear it will command the Mega to start squirting fuel again.
Down shifting and finding neutral will be done completely mechanical with present paddle shifter setup. If the electrical system fails I will just continue using the paddle shifter in the normal fashion (let off on the gas pedal etc).
By still using the paddle shifter and the cable I don't have to worry about solenoids (air or electrical) etc. And it's somewhat Locost in that it adds the minimum amount of new stuff. It all works on the bench and the time the engine is killed is determined by having the shift completed.
I tried a simple ignition kill with a fixed timing and I found that the shift seems to vary in kill time depending upon the speed, rpm of the engine etc. When it worked it was great but most of the time it just didn't shift at all. If the shift isn't done at just the right moment as the engine dies the car momentum spins the engine and then the reverse torque on the gears won't allow the shift with any reasonable pressure you put on the paddle shifter by hand.
I detailed all this on my website but just haven't been in the mood to work on the car for awhile.