If you do a NIP-65 query for a particular user's information, you should be able to use any relay with write access because those are the relays that user publishes their content to. But I believe the relay you got their note from would be a preferred relay in their NIP-65 list. If so, you could cut out the whole NIP-65 step and just use the relay you got the note from as that relay would ostensibly be found in their preferred relay list. It would be a shortcut.