What exactly does the "Clean Up Database" option do when right clicking on the publication node?
The "Clean Up Database" option does a full explicit re-scan on collection memberships without using any AD change control mechanisms such as the DirSync API in-between, when pulling for delta changes. This Microsoft Technet article explains the DirSync mechanism used to track changed objects in AD after a full rescan takes place:
"Polling for Changes Using the DirSync Control"
http://msdn2.microsoft.com/en-us/library/ms677626.aspx
The "Clean Up Database" option needs to be used when there were significant bulk modifications made to AD such as object moves etc. QCS also does a full re-scan periodically, so even without using "Clean Up Database", QCS will fix collection membership after a given period of time.
