I am Destroy()-ing actors and I have same issue, my actors are attached initially to others, I detach them and destroy them, plenty of (Deleted Actor) entries remain in Outliner even if I force call garbage collector like GEditor->GetEditorWorldContext().World()->ForceGarbageCollection(true);
Happens in UE 4.13.0!