Next time it happens, try putting the car into neutral before trying to start it again. If it starts up you may be having a contact issue with your Neutral Safety Switch. The NSS Detects when the car is in neutral and park. If the shifter is in park and the Electrical side of the NSS Doesnt make a connection, the car wont recognize its in park and will not send the start signal to the ECM.
Check out
DIY: Neutral Safety Switch Cleaning
EDIT:
Another thing to confirm its the starter thats causing your issue is to grab a hammer or something hard and have a helper tap the starter the next time it doesn't want to start. After you tap it if it starts, the plunger is getting a bad connection on the solenoids and will need rebuilt. Not a big deal, but you will need to pull the plunger side apart and replace the contacts.
And $400.00 for a starter is just ridiculous !! You can buy a rebuilt starter for $80 - $100.00
http://www.partsgeek.com/gbproducts/...ek+Google+Base