You can't delete the 'NT Authority\Authenticated Users' (SID S-1-5-11) group.
You also cannot view this group in AD Users and Computers, which would explain why you can't see it using that tool.
It's not a "real" security group the way that "DOMAIN\Domain Admins" is, for instance. The membership of "Authenticated Users" is dynamically generated and represents everyone who has authenticated to do the domain.
Edit: Actually you can view it as a Foreign Security Principal in the ForeignSecurityPricipals container. It was wrong of me to bluntly state that you just can't see it in ADUC. But keep in mind that this FSP is not the actual object itself. You can even delete that FSP too... I just did so in my lab to see what would happen. But deleting a FSP is not the same as deleting the object it represents. You can still resolve the SID to name, you still get NT AUTHORITY\Authenticated Users in your token when you log on to a server (whoami /groups
,) and you can still assign the Authenticated Users group to ACLs. All computers understand that well-known SID. Nothing seems to be breaking in my test domain...
I was able to recreate the Foreign Security Principal by adding it to a group. (I added it to the "Users" group for instance.) The act of referencing it caused the Directory Services Engine to automatically recreate the FSP in the ForeignSecurityPrincipals container where it belongs.
I realize that this probably no longer has anything to do with your actual problem - I'm off in the weeds now - but I thought this was neat. Here is me in my domain in which I have deleted the "Authenticated Users" foreign security principal, and rebooted both my DCs. I am still able to translate the SID S-1-5-11 even though the FSP is long gone:
(Then I recreated the FSP by adding it to a group as mentioned above.)