An interesting idea.
Here are a few thoughts on the matter:
The "police" units would probably be formed under a constable and watch system (perhaps a fitting unit name would be "Dogberries" as a little reference to
Much Ado About Nothing.

)
For some balance a city could not have constables
and thieves, the city would have to choose one or the other. Thieves would probably not find it profitable to work in a city with constables and constables would not (we would like to think) want to serve a master who employs thieves. None of the other diplomatic units, namely saboteurs and assassins, would be affected by having constables as those units are more for war-time.
As a trade-off a city with constables would perhaps enjoy a slight production boost (depending on the number of units) for having safer and happier citizens. A cap on the number of units could be placed based on population to keep this from causing an unbalance there, also too many police with too little to do could be a bad thing!
Constables could also be more effective in detecting and catching thieves.
Anyway, just some thoughts on the matter.
BTW: I started this post before any of the other responses so this does not take any of that information in to account.
Edited by Jerec Cross - 13 Nov 2010 at 05:39