> Even if the cops didn't find anything on him they'd ID him for real

Sure thing. They would know what the guy who kinda look like a photo of a wanted man is called. Doesn’t necessarily means they can pin anything on him. Obviously increases their chances, since they can work both backwards and forwards, but that is about it.

Assuming of course that the “he got just unlucky, a random person recognised them” is true, and not paralel construction for some other mean they don’t want to reveal.

Can cops "randomly" ID people in US?

Matching a murder suspect photo is the opposite of 'randomly'.

In some states, under certain circumstances, yes.

is there any country (not currently in a civil war) where they can't do so as long as they come up with a reasonable pretense of suspicion?