We concluded we were not going to be able to get through
to a human decision maker without spending a bucket load
of money on lawyers
Google is not a court. If you want to argue about whether somebody's trademark is or isn't being infringed on, you'll need to take them to court. Barring that, current IP law requires companies to take a maximalist enforcement position like Google has here, or face liability for infringement themselves.If this name was that critical to your business, consider why you hadn't sought trademark protection.
There is a difference between being an responsible enforcer of IP rights and automatically removing apps when they receive a complaint.
If you read the article in more detail, the complaint's only request was that the offending app's name be changed. The offending app complied with the request, but upon appeal Google did not take this into account and offered a boilerplate rejection without considering the facts of the particular case.