In AD the actual permissions are in ADSIEdit, although I'd caution against modifying there. It's a far simpler matter for Exchange Management Shell / Console anyway.

Additionally there's a value in the user (with access) object in ADUC's Attribute Editor, called MsExchangeDelegateListLink. This is set if -AutoMapping is set to $true, and loads into the user with access' Outlook the mailbox they have full access to.

It can be done on the mailbox level or the database level, which would then apply to all mailboxes within that database. If all your mailboxes are showing the same full access permissions then it's probably at the database level. Otherwise, right on the mailbox.

Verify whether it's DB level or not by looking at the properties of your database(s) or alternatively,

For the users that are only SIDs and remain nameless, you can just sub in the SID for the -User parameter, when running these in the shell. You should be able to remove them through the GUI just as easily, assuming you have fingers.

Mailbox level in EMS:

Add-MailboxPermission -Identity UserMailbox -User UserWithAccess -AccessRights FullAccess -AutoMapping:$false

Remove-MailboxPermission -Identity UserMailbox -User UserWithAccess -AccessRights FullAccess

Database level in EMS:

Get-Mailbox | Add-MailboxPermission -User UserWithAccess -AccessRights Fullaccess -InheritanceType all

Get-Mailbox | Remove-MailboxPermission -User UserWithAccess -AccessRights Fullaccess -InheritanceType all

This can also be run in a Foreach loop by piping Get-Mailbox into it and executing the command against the list of objects, assuming the full access wasn't applied at the database level but exists on too many mailboxes to manually run commands against.

These values can also be set in Exchange Management Console. I'm on 2013 so I don't have any screenshots for you, but you should be able to find both in the most obvious places you can imagine.