As spymaster, yes. But as an information gatherer, he has his contacts. And while he would recognize Caddy as an AS, having a connection to the WT would be useful (even if she was a distant contact, he seems like the kind of guy that would ferret out who he was dealing with.) And since Caddy knows Traveling, it would be easy to check pigeon cages around the world. Shrug.

When she said that, I had a feeling about it. Of the people with Perrin, those most important were Tam, Perrin, maybe Faile (though I don't remember if they have ever interacted but she would guess who she is, if she did visit TR) Balwer, and Berelain. Tam, perrin and berelain would be obvious to plans as you said above. Balwer is still a mystery, enough that he will eventually come out with exciting information. Course, it could be that it was just a phrase that BS used to make the end of the chapter interesting.