He was having great success with small and mid-tier companies, then he'd run a pilot with a massive global brand and the results would be even more stark than what he'd see with his existing users. But basically could not close a deal.
Because of exactly what you've shared here: "they measured on how much the spend, not on how much they bring in. Because they've never been able to do that. Their job is so much easier if nobody can ever see that latter figure they just go year to year asking for more budget and the more they spend the more everyone thinks they're doing a great job". I was naive enough at the time to think he was wrong and that couldn't possibly be true. But I've seen enough in the years since to realise he was right.