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:
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).