Ok, this drove me crazy for a while. I was looking for profile of Joost de Valk (clearly remembered he had answered at least once) for plugin developers question, but it was absolutely not coming up in users or search there.
At last I tracked down the answer and profile from there. Which comes up as "Unregistered User" on top.
Are they not search-able for a reason? I don't see much difference between it and regular profile, not being able to search for it only makes it confusing.