Detect Magic. One would think that in a world where magic is common, a guard educated in a use of such spell should be a staple of any organization.
Kings and Queens would probably invest in a full-time diviner to watch their back, one who would know whether inviting certain guests is going to cause trouble.
Regards,
Ruemere
PS. Right now, my players find themselves in a Venice-like city, where Peacekeepers protect ruling class. The Peacekeepers are military intelligence agency consisting of spies, informers, diviners, archivists, enforcers who attempt to detect murders or major crimes in time to prevent them. They are not very reliable, but their reputation, contacts and resources make most major NPCs feel safer.