One idea: on initialization, clients try to open up websockets to a collection of relays. whichever ones successfully establish a connection are published as a parametrized replaceable event with a fixed Kind "K", with "d" tags equal to the URL of the relay. These events ideally would be "sprayed".

Then, as another user, I could query for kind "K" authored by the user I am interested and get the list of relays, with timestamps, they have connected to. By filtering the query I can get the most recent relays, etc.

Obvious privacy concerns. But a good client could prompt user before sending (i.e., "let people know you were using relay wss://XXX"?), and maybe you could set to not send such updates for certain relays.. etc..