As someone who worked in France for a medium-ish size media agency, we had something similar happening to our google adwords account... and it took ~2 weeks for our legal studio to get it back with direct support from google.
Afaik it mostly took them to basically write a few legal letters and telling them "our legal representatives would be glad to meet you at your offices at Google France and discuss such unfortunate issue and so and so" - they basically went "how about no" and restored the account.
Laywer fees weren't particularly cheap (in the range of 2500-5000€) but still well below the money we were losing.
Is this not an option for US-based businesses? I have heard similar horror stories like the one on the OP a few times already but I've rarely seen them pursue a similar path.