Doesn't always work especially on VH (or so I think).
Example, I had captured Alexandria and trained a lot of bishops eventually to convert Cairo, a huge city with a garrison of 2 saracen militia and a few archer militia.
I converted the region to 98% catholicism, had infiltrated with several mid skill spies and destroyed some stuff with assassins. Yet while the PO would initially drop to 25%, the next turn it would be above 100% even though the AI moved out half its garrison and didn't have a race track.

Maybe the AI can prevents its cities from rebelling on VH? wouldn't know.