A method for deleting entries from a directory in which directory information is stored in a set of database tables begins upon a request to delete a directory entry. In response, the directory entry is tagged, preferably by setting the entry's creation time to a null value. If a search query is received thereafter, the routine excludes tagged entries from search results that would otherwise satisfy the search query. Periodically, the routine searches for tagged entries, and references to the tagged entries are then deleted throughout the set of database tables. Thus, the inventive method defers entry deletions to enable directory queries to be processed even if deleted entries have not yet been fully expunged from the directory.