Are you hearing any clicks when it doesn't start? If you are hearing a series of rapid clicks, then you have a problem with the battery, the connections either at the battery or the starter end, or with the alternator or alternator belt. If you hear only 1 click, then you have a problem with the starter's solenoid. This is a common Toyota problem (actually a problem with Denso starters). The contacts inside the starter's solenoid have worn down. Do a search on this forum for starter contacts. It has been covered many times.
Here is a post on replacing the contacts yourself:
http://www.automotiveforums.com/vbul...d.php?t=166530
You can also opt for a new or rebuilt starter, as I did on my generation 4 when it had the starter solenoid contact problem.
Mike