I would go over all the primary electrical cables. Battery connections, solenoid connections, and battery/motor grounds. It sounds like a ground issue to me, but giving them all a cleaning should help out in the future (corrosion is funny in that you can't visually see the layer of insulating muck, but it makes a difference when passing large current like for the starter).
Good luck.