When my car decided to start taking forever to start 2-3 times, then eventually not start, I feared the worst. EGR blanked off already etc etc etc. Even after a moderately long run, it wouldn't start once turned off. I started looking at new alternator/battery etc prices in preparation.
Then I took a closer look at my battery. I removed both the + and - terminals to check they were seated correctly (they were), but when I removed the positive terminal, I noticed it had some sort of oxidised layer (like a layer of metallic paint - you tell me?!) coating the terminal. This simply flaked off when scratched. Reconnected. Started fine ever since.