Is the account you're using a member of "Domain Admins", "Enterprise Admins", "Exchange Oragnizaion Admins" or "Administrators"? If so, you have to remove the explicit "Deny" permission for these groups as well. The "Deny" permission overrides all other rights so it has to be removed.
The way most brick level Exchange backup software works is to have you to create a relatively unprivileged account (in many cases simply "Domain Guest" or some other very limited account group), but give that account "Full Access" rights to the mailbox. We did this years ago with another backup solution, creating an account called "Postmaster". For the legacy tool this account performed the backup of the mailbox data, as well as restores, however, with Veeam we use this account only for restores and it works fine.
We use a simple web based password manager that supports automatic password changes for this account (changed daily) and we "share" this password out to admins who might need to perform restores. The tool audits any access to this password, emailing the team whenever the password is viewed. This provides us with many advantages, including the fact that admins don't have continuous, unaudited access to user mailboxes just so that they can perform occasional restores.