I don’t think there currently is a way to search relays for user profiles by username. Not sure how clients are doing this, but I’m guessing they’re searching cached profiles, so if the profile isn’t cached it doesn’t show up in the suggestions. I’m guessing that is part of the issue. Also, whatever search algo clients are using can probably be improved.
Discussion
damus caches both name and display_name in nostrdb. If there are special characters in the name it doesn't try to convert them into something ascii-legible, but could.
You can't really stop people from putting whatever they want in the name or display_name field, even if its spec'd.
Actually, the nostr.band relay seems to support searching user profiles by name. I don’t think many relays support this though.
Can you tag Ser Sleepy? He’s not the only user I’ve had issues tagging but it’s what prompted this thread. His name has both non-standard characters in it and a space.
I can on Primal, but not on Damus. I think it’s cause he’s using those weird Unicode characters in his name. Not sure how Primal is dealing with that.
It works for me somehow 
Oh yeah now it’s working for me. Prob just wasn’t in my cache.
Didn’t work for me in Nostur or Primal but now if I go back to Primal it does, but still not in Nostur 🤣🤷♂️
I think it’s definitely a caching issue. Decentralization is hard. It’s a million times easier when you can just query a centralized database.
Building an API just for dealing with Nostr profiles seems like a business opportunity
Would be nice if something as basic as tagging another user worked consistently
There a meme here somewhere I can feel it…
unfortunately my API idea would create a central point of failure
Trusted nip05 provider seems like a no-brainer to me.