Just out of curiosity, do you have anything plugged into the center console. The Keyless access receiver is right by the shifter. I have seen Inductive phone chargers and other electronic device wires around the console cause exactly what you're dealing with.
One BRZ had a dash cam cig plug that was made so bad it was causing so much interference the keyless access wouldn't start. Unplugged it, started, plug back in, wouldn't start.
I would try and eliminate any aftermarket anything near the center console, or even remove the console and make sure the keyless receiver isn't damaged or partially plugged in.
