and let's not forget about all the JS (Facebook, Twitter, ad networks, trackers, and so on) that customers love to include on their sites to destroy completely your hard work on having an A score on PageSpeed Insights and YSlow: I just gave up on this many time ago, as you can see in the GTmetrix report mentioned above
I think the problem here is that SEO is a bit of a snake oil business... there are enough charlatans out there and enough site owners who don't understand what is going on.
One way you might consider countering the BS SEO sales pitch is to include it in your own service offering. If you add a bullet point of "SEO services", you can decide if it needs to be an included item or if you want to charge a bit for it, but the end result is that the client feels they have gotten the problem covered (by you), so they are less likely to be taken in by charlatans after the fact.
@espenmn , Thanks for posting this topic. I was having the similar issue and was looking what to do next.Your replies helped me a lot as they were informative and resourceful.