These scenarios always result from watering down actual security.

One time the manager pointed at me and said with a smile, "You're trouble."

There was a (presumed dead) Canadian terrorist with my name.

This is exceedingly dumb if true. Numerical adjacency of SSNs is completely meaningless.

(The above is a joke, I'm guessing US government systems can't handle non-ASCII characters, and a German named Müller would have to be Mueller or Muller)

I don't have a particularly common name but when I google it I share it with an English football player and someone from South Africa who has been convicted of real estate fraud.

I've never been to South Africa but I have worked for a real estate portal, and it's on my LinkedIn (which I barely use, but still). I can see how someone outside would not be able to separate the two.

Go to this tool and check to see if your name is coming up with any returns.

It kinda makes one wonder if anyone getting into a bit of terrorism for a hobby wouldn't do well to change their name to that of someone in the US congress first: no way that name would stay on a blacklist for long.

It wouldn't shock me if even changing your name didn't do it, the name change records are surely data available to the algorithms.

Anything that will help you prove: a) you are who you say you are and b) this is your account will be useful.

And if you're physically in their office, they can and will follow the backchannels to get a better result faster than you can over the phone.

OP, you should buy an Equifax or Experian credit package immediately, review every account, and put a freeze on your credit report. This will be the best twenty bucks spent in your situation.

They refused to give me any clue how to address their concerns, so I just moved my accounts — all of them — to another bank. But that was mostly out of spite, not because I believe the new bank doesn’t have equally troublesome possibilities.

BTW, I have got to be about the least risky imaginable person to open an account for.

I would go after the most important accounts on the real government based Justice system (and forget about any non-important one). But I'm not from the US and I don't know how binding are those agreements that you won't seek the Judiciary. (Anyway, arbitrage should be fair enough to let your point through, but I don't know how accessible it is.)