OK, I think I've posted this four or five times over the course of the last few weeks, so I figured I'd post it here for easy reference. If the TC could amend the first post under "Lords & Companions" for easier reference, that'd be cool, too.
All companions are associated with a town; by sending them on a "reconnaissance" mission, they will bring you back all sorts of information about the faction that currently owns that town, including the relation of the vassals to their liege. They'll be gone about 5 days. They will always give you information about the faction that owns the town at the moment they report back to you. So if the town changes factions while they're away on their mission, their information will always be the newest owner rather than the one you originally sent them out to get information about.
Here are the companions and the towns they are associated with:
Alayen: Reyvadin
Klethi: Khudan
Baheshtur: Tulga
Borcha: Ichamur
Jeremus: Halmar
Deshavi: Tihr
Marnid: Sargoth
Ymira: Yalen
Firentis: Uxkhal
Matheld: Wercheg
Katrin: Praven
Nizar: Suno
Bunduk: Jelkala
Lezalit: Dhirim
Rolf: Veluca
Artimenner: Narra, if he's bugged; Durquba, if he's working properly. He will always say Narra, but if he's working properly, you should get info from the Sarranid Sultanate (as long as they still own Durquba, that is).
As you can see, most factions are well-represented, but the Vaegirs only have 2 towns represented, and the Sarranids are very underrepresented, with either only 1 town (if it's working properly) or none at all (if it's bugged).