I recently came across this error when creating a service account for BitTitan during an Office 365 mail migration.  BitTitan requires the account permission to each of the mailboxes in prep for the migration.  When attempting to Add-MailboxPermission on all mailboxes in our tenant, I received an error on the MaxEnvelopeSize quota.

Request size exceeded the configured MaxEnvelopeSize quota:

Get-Mailbox -ResultSize unlimited | Add-MailboxPermission -User username@contoso.com -AccessRights FullAccess -InheritanceType all

Sending data to a remote command failed with the following error message: The WinRM client sent a request to the remote WS-Management service and was notified that the request size exceeded the configured MaxEnvelopeSize quota. For more information, see the about_Remote_Troubleshooting Help topic.
+ CategoryInfo : OperationStopped: (ps.outlook.com:String) [], PSRemotingTransportException
+ FullyQualifiedErrorId : JobFailure
+ PSComputerName : ps.outlook.com


I have seen in many cases the issue is resolved by increasing the MaxEnvelopeSizeKb default size from 500kb.  This can be done by running the following PowerShell command.

Set-Item -Path WSMan:\localhost\MaxEnvelopeSizeKb -Value 2048

In my case this did not work for Office 365, I still got the error when running the Add-MailboxPermission command.

The fix was to run the Office 365 command from my Windows 10 desktop and not a Windows 2016 Server.  Since it does not have the service it eliminated the issue.