Igor, that's odd that it's behaving that way even with nothing in gatewayProxy. Unchecking "Automatically update" will certainly stop it, though. Native mode shouldn't change the behavior at all.
Dan, your understanding is correct. After changing the department to reflect the new business unit, the user's email addresses will remain unchanged unless you "Apply This Policy Now", which will cause the RUS to evaluate everyone under that policy. However, if you are running the RUS on a 2003 Sp1 server, you could use the new GUID that was added for the migration wizard. In answer to an earlier question I said that this GUID signals the RUS to stamp any missing secondaries, but really it triggers a full application of the policy against that particular user - including primary addresses. Populating msExchPoliciesIncluded with the following value should effectively cause the RUS to apply the policy to just that one recipient:
{23668AD4-4FA1-4EE8-B2BB-F94640E8FBA0},{26491CFC-9E50-4857-861B-0CB8DF22B5D7}
Unfortunately there's no way to do this automatically except through the Migration Wizard right now. However, you could easily write a script or make your own extension for ADU&C that would do this.