An nprofile could be useful, it includes relays. I've mostly only had issues with some npubs taking awhile to find.
https://github.com/nostr-protocol/nips/blob/master/19.md#examples
Challenge with searching by names is potential for a lot of fake duplicates, and be quite confusing. Using a follow graph as a web of trust could work, some clients might do this for searching for npubs to mention.
For a name instead of an npub or nprofile, domain names that redirect to a nostr nprofile (with a fallback) can also work well. I've tried 307 redirects and it works, however an HTML page has the option to display something if there isn't a native client available. Could be also a good use of njump.