Just had this problem last week actually. Ended up being cracked wire going from the battery to the main Fuse set (car is 18 years old). The quick heat up and arcing would cause starts to be nothing more than a click (with all the lights going out in the car). It wasn't a slow creep up either. It was working when I left for work, stopped to get gas about 6 miles down the road, got back in, tried to start the car, and it wouldn't start at all.
Loose battery terminal connections can cause the same issue. Checking the wire and the terminal connections might be worth while if you've already ruled out the battery.