Only agnecies who have lots and lots of clients are getting enough of an overview to test techniques in a repeatable way, across industries, audiences, etc. This one appears to have less than 10 employees and listed SEO last in their own list of services - suggesting maybe one or two staff who do a bit of it.
There is no way you should be handing over tens of thousands to someone who clearly doesn't have a lot of experience in SEO. They can only give generic entry level advice and hope for the best, which is exactly what this client got.
Is a big agency a guarantee of success? Absolutely not. But a tiny agency is almost a guarantee of failure of ROI. That said, I have known some very smart self-employed consultants in the industry, I don't want to tar them with the same brush.