Yes, they could use a relay Explorer to track notes and match with pubkeys.

This applies to private/premium relays too, as most of them only forbid write access to select pubkeys and not read access. This means the relay Explorers can still view notes.

Example, my own premium relay, the notes published can be viewed:

https://nostrrr.com/relay/nrelay1qq08wumn8ghj7un9d3shjtnkv4exjenfv4jz6mn0wd68ytnrdakspvd95r