Random starter trouble

I agree with a loose wire somewhere or a bad battery.

If not either of those, then I would start to suspect the starter. Just because it was rebuilt, doesn't mean it was done right. When my son got his valiant, he bought a new alternator and it didn't work. Returned it and then asked them to test the "new" one before we took it home, it was bad - right off of the shelf. We had to go to different outlets of that store and three in a row right off the shelf could not pass the alternator load test.

We then went to an old "Ma & Pa" shop that I knew from the old days who does a great job and tests them before giving them back to you. BINGO! It worked fine the first time!

If you find a good reliable builder - cling on to him like grim death.