Brake light switch worked for me
just to contribute to this thread -- I had the same problem with the auto shifter stuck in park (a 2006 Forester). After reading the suggestions above I took off the paneling of the transmission, cleaned everything up including that solenoid that unlocks the transmission when stepping on the brake, and used WD40 on the switch at the top of the brake pedal. Then I drove around for a while and waited for it to happen again. It took a few days, but eventually it did, and it was clearly the break pedal switch because my brake lights weren't going on. I even noticed that the switch was coming out as it should when I press on the pedal, but still no lights ... so definitely a defective switch.
I then searched online and found the part on ebay for US$6! However, I needed it done asap, and the only ebay parts at those prices were from the US. We're in Australia, and I couldn't wait that long (I think driving without brake lights is illegal after all), so I had to get the part at a dealership here -- cost me AU$54. Crazy what a difference that is.
Anyway, I replaced the switch, only took about half an hour, and haven't had the problem since -- all sorted! This is definitely an easy DIY job, it's a bit fiddly to get to, but not hard to do.
However, just in case anyone else has this issue -- since I drove to the dealership with the switch already out, the check engine light came on. This worried me (had I knocked any electric wires by accident?) but now a few days later that's turned itself off -- apparently the car computer detects when things that seemed wrong have righted themselves.
Happy tinkering and a massive thanks to all those giving advice on this -- you probably saved me $100 or more in repair costs, much appreciate it!