Intermittent push to start: the demon that continues to torment

1993 Geo Prizm, manual transmission: Intermittent failure to start over a two year period, gradually becoming more frequent. The engine turns over every time the key is turned to start the engine, i.e. the starter motor/battery/battery connections work flawlessly. Once started the engine runs flawlessly without misses or shut downs. The only possible problem may be the engine idle speed that seems at times to be too high even after the engine is warmed up. Without predictability, the engine may fail to start when the key is turned. Remember the engine still turns over normally. It just does not fire up. Two options exist for my predicament. That which is resorted to the most because of the speed of recovery: step out of the vehicle and push start the car by popping the clutch. The other alternative which I have been forced to utilize before because of the physical impossibility of push starting (i.e. if I had been able to push, I would have popped the clutch to start) at the time has been to wait for a protracted period and re-attempt to key start the car. This has been successful a couple of times.

When was the last time the car had new spark plugs, air filter, and other basic maintenance done?