Hi Cesar,
thank you for clarifying the "memberOf" thing - I always wondered why some users weren't synced like expected, but a few days later they were in sync - probably of some change I didn't notice (bad password time...)
I also saw that whenChanged seem not to be propagated between multiple DCs, which has the effect that I had to use a distinct DC for syncing...
...and thanks to Axel Faust and the others who work(ed) on the OOTBee Support Tools 
I don't think the users are cached but not deleted by now. You can see this in the user administration (admin console). Because your ...allowDeletions flag is true, all you need is a full-sync.
Your can force this by temporarily setting the differential query to the same value as the full query like Cesar Capillas mentioned above, and restart alfresco.
But alfresco has already created a user home for each of your users. These home directories will not be deleted (this is normally a good thing, because you don't want to have user-data deleted when you accidentally misconfigured the sync).
Make sure the value of synchronization.allowDeletions is really true, because if set to false, all your unwanted-synced users will only be untagged and converted to local users (uahhh). But this is explained in the docs http://docs.alfresco.com/5.2/concepts/sync-delete.html
I fear you'd have to write a script to delete the home-folders of the non-existing/allowed users. Maybe someone in the community has done that already.
...or you just don't care about the unused folders - but they can behave bad, when you sync a formerly not allowed user. Then a second home folder with a number added to the username will be created.
...I should setup a knowledge base for things like these with a sophisticated solr/elasticsearch index
Thanx again Axel
