I've got a '94 Turbo (144K miles) which has just started exhibiting this problem. I've been lucky to have had it happen three times where I was able to try some stuff. On the advice of my local indie I pulled a plug wire to check for spark (screw driver from plug socket to block). On each occasion the car started immediately! On the '94 and earlier Legacys the cam/crank sensors are a bloody fortune (more like $200/$300)!
Anyone have any idea why removing a plug wire (this happened to be #1) could affect this?