DeleteEntries can return a warning, MAPI_W_PARTIAL_COMPLETION, to indicate that it couldn't delete one or more of the entries. Test for this return value with the HR_FAILED macro and call the container's IMAPIProp::GetLastError method if more information about the problem is needed.
When you hold a pointer to a deleted entry's ADRENTRY structure in your cache, you will still be able to retrieve properties using its entry identifier. This is because the entry is only marked for deletion. MAPI maintains a level of access to these marked entries by design.