I have had this same problem. A few times it has started and run on a couple of cylinders. The had time it ran like this I shut it down and tried to restart it and then I was dead. I have a high mileage engine (147K) and the cylinders were pretty well washed down and that makes it worse because of the loss of compression. When I absolutely could not restart, I had mine taken to the dealer on a hook too.
The mechanic came out and interviewed me and we were able to eliminate a few things but he did find a small vacuum leak, but that was not the problem. I should have let the car run and let it sort itself out and it would have been fine because the cold restart just put that much more fuel in the cylinders. He pretty much said the same thing. Short sart/shutdown cycle leaves the cylinders wet for the next restart. He did suggest 87 octane fuel as it vaporizes better and fires easier. I do not notice a performance difference and the sensors keep it from knocking. I read an article in a petroleum engineering journal that said that even cars that call for premium use 87 octane due to the computer adjustments of the timing, etc. Many manufacturers spec out premium fuel for expensive models because the consumer "expects" it and it is part of the entire status emotion that drive new car sales. I do run a tank of premium every 4-5 tanks though, just because the fuel cleaning additives are not in the low octane fuels. Those additives really work. I saw the data and examples of deposits in testing at Texaco Research (former customer) when they were developing the System 3 additive package. made a believer out of me.