I know it sounds ridiculous, but the last two times I have seen this, the battery connections themselves were loose. Only put on by hand and the connection just wasn't good enough.
Don't go by what they "look like", either. You can learn to quickly make tests with a test light/ meter and KNOW. CLEAN the terminals and clamp. Get a good battery post cleaner tool
