I think that asking when a relay is unknown is an effective strategy, that doesn't ruin the UX.
You can always check the already approved relays first and try to fetch the note from them, this would slow down the loading a bit, but it makes the process completely transparent for a good amount of notes/profiles.