It turns out that the factory wiring for the starter solenoid just
barely meets the amperage draw requirements for the starter to engage.
Even worse, the powersource comes from the actual ignition wiring. Over
time, the connections corrode and the starter solenoid, as it ages,
requires more amperage in order to engage the starter. The factory
wiring is simply not up to par. You might notice that turning off the
AC, stereo, radar detector, etc will sometimes help it start without
clicking, this is because basically all the electronics in the car are
fed through a very small connection from the battery. A turbo timer, if
you have one, also draws its juice from the same line as the starter
solenoid.