To put it simply, the messenger was a very visible pawn of Graendal's. Graendal of all people knows that's it's very hard to completely erase something from the human mind, especially a location like Natrin's Barrow where that mind was subjected to the shock of Compulsion. There's always the chance that people might have some memory of the location, and that if Rand comes searching for her, he will look firstly at high-profile Domani messengers since LTT knows that's how Graendal would operate.

To counter this, she used a much more subtly-positioned servant working in a prison (Kerb). Rand would not have gone looking for him (and indeed, he didn't - Nynaeve did that). Furthermore, it seems like a lucky coincidence that Nynaeve caught Kerb out - had Rand gone there, he would have failed to sense the saidar-compulsion.

Regardless, I do tend to agree that this plot mechanism for finding Graendal was a bit weak and "lucky" for the Light, but I still don't find it to be a "major logical flaw", let alone implausible.

For all we know, the messenger had other orders, perhaps including one to return to Graendal's lair (even if she couldn't vocally reveal its location), and had to be killed for that reason.

So in summation, Graendal is dead and I don't have a hard time believing any of the events that lead up to it. It might not have been the most imaginative writing, but it was decent enough and the payoff at Natrin's Barrow was worth it.