After an object is deleted it will remain in the directory for the tombstone-lifetime (60 or 180 days by default). The tombstone-lifetime assures that the tombstone will be replicated to every DC, so that every DC knows that the object is deleted. This is the reason why you cannot use a backup to restore Active Directory which is older than the tombstone-lifetime - it would reintroduce objects which have been deleted prior.
The garbage collection process one every domain controller takes care that tombstones which are older than the tombstone-lifetime are deleted permanently. The garbage-collection process runs by default every 12 hours on each DC. You can also configure other periods by modifying the garbageCollPeriod Attribute of the CN=Directory Service,CN=Windows NT,CN=Services,CN=Configuration,DC=yourdomain,DC=com Object.
However, the object is permanently deleted now, but the NTDS.dit Databasefile which contains the Active Directory will not decrease its size. Instead the new "Whitespace" will be used for new objects. The only possibility to release the Whitespace in the database is to perform an offline defragmentation using NTDSUtil in the Directory Services Restore Mode.
