In the very off chance that its not the same HD wallet, I just don't understand why "different users" would entrust each other with their private keys unless they were very close, or more likely, the same person.
I've been entrusted with private keys on multiple occasions. I can also imagine someone uses someone else's addy to join a certain campaign, for instance because he owes him money, or because he's not interested in weird "tokens".
It's all possible, just not very likely.
Even if entrusted with somebody's key, you would not import it into your own wallet and intentionally merge it with your coins while you are safe-keeping it. It would just be a made up lie.
My assumption was the addresses were random.
No. Pseudorandom at best. Read about derivation paths in HD wallets in detail. You can use the xpub to deterministically derive the children. HD stands for hierarchical deterministic for a reason.
I know about xpub (but never memorized the exact details): as far as I know, it's not possible to know addresses are derived from the same xpub unless you know xpub, right?
That is correct.