OP, was that your own computer/profile that you emptied the Deleted Items from?
If tech support stories are to be believed, many users use that folder as a one-button-press archive and the idea that things might actually be deleted from there is both incomprehensible and then horrifying to them.
It also might explain why the icon is an old one because Microsoft's quality control teams probably use the feature this way and never once saw that icon, leading to it never being updated.