To recap:
-Long cranking, but turning over like normal
-Fuel pump priming
-Battery/ Charging system checked out fine
-When car fails to start, it can be push started
Correct?
I'd forget the starter right off the bat. If it sounds like it is spinning the motor normally and quickly enough to build compression, it is doing it's job and the battery is as well. Does your "check engine" light illuminate when the key is in the on position (engine off)? Have you had it scanned for any "pending" codes?
Like Don was saying, arm yourself with a few things so that next time this happens you can run a few simple tests. Leave the spark plug cover off of the front bank as well. Bring a can of ether, a spare spark plug and a "jumper" wire with two alligator clips on either end. If and when you run into a no-start first test should be spark- don't worry, you won't need a friend with you. Pull a spark plug wire, shove your spare plug in there and use the jumper wire to ground the plug to the block. Setup your iPhone to record the plug hopefully making a strong spark. If you have spark, proceed to shooting some ether lightly in your throttle body. Don't forget to put the snorkel back on before you attempt to start it.. If it fires and stalls then its a fuel issue. Culprits? Fuel pump, cam/crank sensors, ECU not grounding injectors, and unfortunately many other things.
You suggested the ignition switch- its slightly possible. In the start position, the starter circuit is energized (obviously) but the ECU needs to remain powered in order to send the commands for spark and fuel. It will be a little more challenging to test this but knock out the first couple tests and post your findings. Good luck!
One last thing- I had this happen to a v6 contour I worked on and it ended up being the coil. It wouldn't start and after a few attempts it did but ran like crap. Did some tests and swapped with a spare coil and it ran right away. No MIL codes showed up either.