Without going fully whackadoodle conspiracy nut and trying to sensify everything…
I dunno if I see too much Ethereal in her garments; she has some leg bandages going on, but the rest of the fit lacks the shiny metallics they have. To me, it’s closer to the Nightborne and Void Elf heritage armors, with a mix of Kael’thas shoulder orbs.
Locus-Walker’s familiarity with her doesn’t really surprise me much. If Dimensious liked Xal’atath enough to give her a staff, Locus-Walker would be keenly interested to learn more about her. Given the Black Empire would most likely predate K’aresh blowing up (mostly because otherwise, Locus-Walker and the other Ethereals are in the tens of thousands of years old ((the Ordering of Azeroth, which ended the Black Empire, happened before Sargeras converted the eredar to his cause)), while they “only” say K’aresh blew up thousands of years ago), the most probable situation is that Xal’atath had already gotten the Voidstar before Locus-Walker even knew about Dimensious. So learning about Big D’s past and finding a Xal’atath in it seems the most likely scenario. Or a Xal’atath weilder was involved somehow. But meeting Xal as an entity doesn’t seem plausible, given what we know.
The void naaru bit I never noticed until you mentioned it, and now I cannot unsee it. My best guess here is to go back to Xal’atath’s whispers which are absolutely definitely totally not lies. Brethren, true masters (meaning the Light wouldn’t be their true masters), it all hints at a silly-dumb possibility that the Naaru actually serve the void. Or did. Which yeah, could explain the weird void state they get, but I really hate that idea and don’t want to give it much air.
The moon symbology is undeniable though. The tattoos/scars, her eyes looking like a solar eclipse, it’s there and meant to draw our attention. It’s deliberate, so there has to be some connection. And then there’s how she refers to Elune; an “upstart goddess” and a “great enemy” (Sisters of the Moon: “the shrine of a great enemy”), implying there’s more than some passing familiarity there. Respect and hate.
I suppose one possibility could be that when the void lords vomitted old gods out into the cosmos in the hopes some might land on worlds, and some of those worlds might have titans, Xal’atath might have missed the planet and splattered on the Blue Child, then eventually fell to Azeroth to be forged into the Black Blade. And now I’m going all whackadoodle crazy-brained, and I think I might go to bed.
… She could just turn out to have been a really powerful troll shadow priest in the Black Empire days, and I think I’d be okay with that too.