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.
This, nprofiles helps for a robust discoverability; nip-05 (that can contain hints) make things easier with a memorizable and uptadable entry point.
Search by name (or nip-05 substring) can be more effective simply showing first the followed and then ranking by followers count (should be easier to cache that reconstruct a social graph).
Yeah, makes sense. It could be possible to keep a cache of the follow graph local for quick usage. Perhaps update it at some interval, or when profiles are loaded.
