I had a similar problem with my Honda, about the same vintage (1994). Lets get more info. My issue was temperature dependent. - cold would start, hot would start, warm would not start. It sounds like your issue may be temperature dependent also, starts hot, does not start cold, does not start warm. Is this correct?
If that is the situation, you need to test each of the systems (when it is cold is a good place to start, and easy to repeat). The systems you need to test are fuel and spark. Lets start with spark, it is easiest. Go watch a youtube video about testing the spark on a 1994-1999 Subaru. Do not buy any equipment, just make sure ONE of the spark plug cables sparks to the block when you crank it (this is a 2-person job unless it is very dark). Use the easiest spark plug cable to get at, disconnect the spark plug end, put an old (or new) spark plug in it, and lay the plug on the engine block so the metal part of the plug touches the metal of the block. Make sure you keep the spark plug away from the alternator, as the alternator could be damaged by the 10KV+ spark.
If you have spark, sou probably have a fuel issue of some kind. There is a relay which turns the fuel pump on. On my Honda, the Printed Circuit Board that held the relay had a "cold solder joint", which developed over several decades, and which was caused by the vibrations all components in a car are subjected to.
Replace your fuel filter unless you have replaced it in the last 12 months or so. Then retest to see if that fixed the issue. Doing that properly will teach you a few things about your fuel system. Be extremely careful. The fuel systems on modern cars are very high pressure systems, so one connection not properly done and checked can spray gasoline on your exhaust manifold, and your car is on fire and burns to the ground. Feel free to have your mechanic replace the fuel filter, but do not expect him to diagnose your problem. He does not care. He removes things and replaces them with expensive new parts. That is all he does. Tell him what to remove/replace.
The push start is the biggest clue so far. As Joel noted, when you push the car, the starter motor does not have to work hard, so the voltage is higher, which gives you a better spark. The starter motor could be part of a complex problem. It is clear to me that the battery is not the issue. You cranked the engine via the starter many times before the push start worked, so the battery is fine. Get a Digital Volt Meter and do a two person test, monitor the voltage across the battery while you try to start the engine and it fails. Do not run the starter more than 8 seconds before giving it a full minute to cool off. Damaging your starter could make this problem worse. If the battery voltage drops below 8 volts during the test, and returns to 12.8 volts after the test, that low voltage is going to prevent the ignition system from generating a healthy spark.
If the cranking voltage test fails (less than 8 volts), please post comments here. It could be that the starter has an internal short due to being overheated, and that is the root cause. It is also possible that the ignition system is a bit weak, and that is contributing to the issue. I have seen both issues, separately, and together.