Sounds strange.
I'd have a look at the battery clamps and make sure their making good contact in case their causing some resistance. Then every possible connection between the battery and starter. If you cant find the problem, you might drive it locally with your tools in the car until the problem occurs and then start testing. I can probly give you a bit of a guide but i'm sure theres more qualified people on the forum.