Users choose pubkeys, not (primarily) relays. Relay selections are downstream from pubkey selections. A client cannot choose the correct relays for a pubkey without considering what relays that pubkey uses.
Regarding proxies, you're right that if a client doesn't support proxies, they don't support proxies. Clients should support proxies. But if they do, the proxies need to support outbox.