I'm not a lawyer but it occurs to me that he might try legally changing his name-- not in a meaningful way, but by, for example, adding an unusual middle name. That just might do it. And getting Global Entry documents is another good way to avoid problems, that takes a small fee and some paperwork.

I agree, in my experience, the rules are whatever they make up at the time. I have some wildly annoying stories myself.