The first thing that I do in these situations is to thoroughly clean the battery posts and terminals until you achieve bare metal. Sometimes you get an oxide scale that is not very noticeable but will still cause intermittent starting problems. Good Luck.
Exactly ! Do not over look the grounds , all of them that you can locate .