Evan, if you test your last sentence towards exchange 2007 you will discover that it isn't true. The (only?) action that the new (higher) policy, now matching the recipient, guarantee is the stamping of new addresses and the changing of primary address. But ALL previously stamped address (from older policy now out-of-scope) REMAIN stamped to the recipient.
So, for example, in a multi-internet-domain environment like a multi-company group, when a user switch from a company to another (or from a division to another) having different internet domains, he/she maintains old company addresses (stamped by old policy), making the whole organization an "addresses chaos" in a few policy-changes.
The current policy behaviour results unmanageable other than in very simple cases. The stamped addresses are actually unpredictable, due to policy in/out of scope.
In my opinion there are two possible solutions:
1) you move out-of-policy checkbox to address-level granularity, introducing some sort of "added" or "special addresses" to a recipient which they remain unchanged when the recipient changes the matching policy
2) you make more rigorous the application of a policy: if a recipient stay controlled by policies (with the checkbox), it always get exactly the addresses from the higher policy it matches (in other words, you clear and then re-generate all stamped address).