It looks like once I delete and object from a scene, UE still thinks this object is needed for the scene and tells me its missing.
One of the ways to fix this is not just solely restart Unreal Engine but to delete the [SAVED] folder from the project.