About one in twenty times I try to start my 2005 Subaru outback, it doesn't start. However after periodically trying to start the car, it will usually start within 1 to 6 minutes. Here is a video of the car not starting. This problem has been going on for about 3 years. It is not the battery since I had that replaced within a couple of months of when the problem began. I have an outback 2.5i which according to cars101.com does not have an immobilizer key.
I have the same car.
I would recommend getting an inexpensive multimeter and learning how to use continuity mode which will tell you if two wires are connected or not.
Next time you get a no start condition, use the multimeter to determine if the starter solenoid is getting the signal to start. If the multimeter indicates continuity, you know it's your starter.
If there is no continuity at the starter, you know the problem is further upstream. There's several switches that can prevent the signal from getting to the starter. Transmission safety switch (only lets the car start in Park or Neutral) or clutch safety switch (only lets car start when depressed). There's also the ignition switch itself (that's the switch that is activated when your key turns).