diff --git a/service/src/com/android/server/connectivity/PermissionMonitor.java b/service/src/com/android/server/connectivity/PermissionMonitor.java
index 1bab186..3bf7fdc 100755
--- a/service/src/com/android/server/connectivity/PermissionMonitor.java
+++ b/service/src/com/android/server/connectivity/PermissionMonitor.java
@@ -1027,8 +1027,10 @@
         // exclude privileged apps from the prohibit routing rules used to implement outgoing packet
         // filtering, privileged apps can still bypass outgoing packet filtering because the
         // prohibit rules observe the protected from VPN bit.
+        // If removing a UID, we ensure it is not present anywhere in the set first.
         for (final int uid: affectedUids) {
-            if (!hasRestrictedNetworksPermission(uid)) {
+            if (!hasRestrictedNetworksPermission(uid)
+                    && (add || !UidRange.containsUid(mVpnLockdownUidRanges.getSet(), uid))) {
                 updateLockdownUidRule(uid, add);
             }
         }