I see where you are coming from, but I'd say time complexity in this case isn't as much of an issue. Sure, n^2 isn't great, but since the information being passed around is so minuscule, I don't see it making a game-breaking difference.

Using Python, I just made a quick n^2 operation (which is not a realistic comparison by any means, but just for the sake of this..) assuming that the worst case is that for each of the 5000 players, 5000 messages needed to be sent. And I really hope they didn't make it that bad!

This test took Python on my little machine ~2 seconds to accomplish. On something Blizzard has, that would easily be reduced into a 10th of that time. And, Python is super slow (see https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/gpp-python3.html).

I also believe the client/server of WoW back then was built with a lot of C++, and every piece of information you see in game is handled via massive databases (O(1) at best, O(logn) at worst to fetch).

TL;DR Ignore my bored nerd rant: n^2 sucks. But it should be able to handle at least 5,000, if not 10,000, in one spot with modern tech just fine.