Add-RecipientPermission You can't use the domain because it's not an accepted domain

I'm trying to give my user SendAs rights on a shared mailbox. Both the EAC and Exchange Online Powershell give me the error that I cannot do it because "You can't use the domain because it's not an accepted domain for your organization.". I have verified that the user does not use any alisases or email addresses that are not accepted, but it still won't do it.