Did you try twisting the battery terminals at the battery? Corrosion builds up and can create resistance. Same goes for any other electrical connection related to the starting system. The connections at the starter are less likely to corrode since they often get a thin (or thick) coat of engine oil from leaks!