That's a very good point Strynboen. Sometimes dirty terminals can pass low currents but not high currents.
lowmileage,
Yup, I meant the large main cable running to the starter from the solenoid.
Pulling out the starter and testing it directly off the battery as Strynboen suggests is a good idea too, that'll tell you for sure if the problem is the starter or the wiring, but that involves pulling out the starter. Your call on which approach to take.
Another possible source of problems like this is the internals of the solenoid itself. Inside, there's a plate that gets pulled into contact with the terminals of the main cables when you energize the solenoid, this bar can become corroded or scorched and stop passing power. You can test for this by testing resistance across the main terminals (big wires) when you press the start button, resistance should be very low while you're pressing the button.
mystic_1