Do you know if the fuel filter has been changed? Lots of places quietly skip it as it's a pain to do. But in my experience an old, clogged fuel filter is often the reason for poor starting which wrongly gets put down to battery, plugs etc.
Mine did this even with a fully charged battery , turned out to be a poorly attached earth to the battery. Worth giving it a tug and seeing if it comes off
First of all, check (clean and grease) all connectors between battery, relay and starter motor; also clean connector on earth wire bolted to engine and earth wire fitted to ECU. Next step good battery, gel would be better than acid.