If I read your question correctly, it is not one of how to manage the actual permissions applied, as it is knowing when you neeed to change those permissions.
As I see, you can approach this one of two ways (NOTE: Neither one will be 100 percentsuccessful unless you have upper management "buy-in"):
1. In most companies, the one organization that almost always knows where everyone is is HR. Get together with HR and hammer out a policy whereby HR will notify IT whenever an employee switches departments. Be aware that this might meet with some resistance as it requires extra workload on the part of HR (remebering they need to notify you and actually following up with notification on a timely basis).
2. Put the monkey on the back ofthe department heads. It is probably in the best interest of the employees former department head that the employee no longer has access to data/ applications under his purview. Therefore he needs to notify IT when an employee moves elsewhere. Itis in the best interest of the gaining department head that his employees have access to the data/applications necessary to work efficiently. Therefore, the gaining department head needs to notify you any time he gains a new employee. Again, this is likely to meet with some resistance in that it will increase the workload of department heads to remember to notify you of employee changes. Also this route is more likely to need upper-management buy-in as these middle managers are more likely to bend upper management's ear if they don't like this process.
Hope this helps (and yes I am needling both HR and middle-managers just a little).
