Someone recently posted on this issue describing a failure in the wiring. He had replaced with high quality 0 gauge, and that too eventually went bad. A lot of amps going through copper eventually causes what I call "black wire disease", and you usually see it on the ground side of the connection. The jacketing looks fine, but underneath the wire looks all black and corroded with specks of blue and orange.
It's hard to tell visually from the insulator jacketing whether a wire has gone bad. May want to go over the obvious connections with a multimeter before you rush out and get a starter. Usually, a bad starter will not work at all because the brushes are fried, the bearing is shot, etc. Pretty rare to see one intermittant, but not impossible I guess.
Otherwise, sounds like the starter.
o/______\o
(Oo=00=oO)
[]=****=[]