Stubs from a Subscription are not being removed from the GAL when they were deleted from the Publication.
All of the objects that were not deleted were created the same way. They were originally created normally. They were then moved to a temp OU and the subscriptions were removed. They were move so they would not be deleted when the subscriptions were removed. Matching was then setup and the subscriptions were re-added. Once they were re-synced, the objects were moved back to the stub container. The ACS addresses or extentionAttributes were not removed before resycing and matching them.
If the stub object was created with external matching, then removing it from synchronization will not mail-disable the object because by the QCS security model, QCS does not "own" the external objects and is not allowed to do anything with them except for synchronizing selected attributes. So, what you are seeing (not removing stubs from AD when removing them from collection) is normal behavior in this case.
The following procedure will remove the deleted stubs:
1) Move stubs out of QCS OU to the temp OU
2) Setup automated DELETION on this temp OU so that QCS automatically deletes these objects and create new ones (all important attributes like LEDN and group membership will be preserved).
3) Re-publish the collection from source, this would delete all objects from temp OU and create proper "normal" stubs in QCS OU
4) Delete remaining objects from temp OU after initial sync is over if they are not needed
Development noted that this procedure is unusual and could not say what would happen with external stub after it is moved to the QCS OU. This form of product usage was never Quality Control tested, therefore the outcome maybe problematic.