I spent much of the past 7 years or so doing this exact same type of campaigning with my clients. I have always advised metadata over folders, for the reasons you've listed plus many more.

However, since the widespread release and rapid adoption of OneDrive for Business, it has become very common to sync SP doc libraries to our local PCs or handheld devices, since this gives us the great Dropbox-like experience that has become such a common way to collaborate on documents. You get seamless offline capability, you never have to use your browser to get to the documents, you get to leverage your OS's native search functionality, etc.

The issue is that when you browse the document library on your local device, the metadata is unfortunately useless (it is nonexistent), and you are left weeding through a flat list of hundreds of documents with no organization whatsoever. Consequently I've begun to change my position over the past year or so, and I've started using folders more (which I never thought I would succumb to), because it makes the OneDrive experience much better, and that is the way most of my teams are collaborating these days.