I had a single territory of Parthians completely surrounded and cut off from it's main force for many, many turns (That idiotic province hiding in Eygpt, I didn't notice it) and no major rebelling was going on there at all, despite the fact that it was completely isolated and surrounded by hostile forces.

A bit unrealistic IMO. In a scenario like this, the town should be considered "under siege" and apply all the appropriate penalties.