"How many people do you know with adjectives in their name? If you met someone and they said their name was "Joey Red Puma", would you assume that's real or fake? You'd probably say something like "really? you're joking, right?" I would certainly be skeptical."
Nope, I grew up around people with adjectives in their name. It is very, very common among the plain tribes[1]. I tend to be suspicious of people named "Smith" or "Johnson" since it seems like a common dodge on forms.
I am troubled that you think having an adjective in a family name should be cause to trouble someone. I realize European names have suffixes added in place of adjectives, but that should not blind people from other ways names are assembled. I am also particularly unhappy with an American company that has heuristics that flag a specific ethnic group in the USA.
"the best you can do is use heuristics to try and approximate a good solution, since the "right result" is simply impossible to compute."
Then don't friggin do it. Google is a SEARCH company and has indexed a huge amount of the web. Running names through their damn heuristics should have shown a problem. If you google "Yellow Horse" you see multiple examples of people with that family name on the first page of results.
Google especially shouldn't try it since they don't have support needed to handle the exceptions without people going to the press.
1) not sure about south or east or 1st Nations