Send As permission on Office 365 not with Add-ADPermission
With an On-Premises Exchange 2010 environment an administrator hands out Send-As permission with the Add-ADPermission cmdlet.
But I found out that this doesn’t work in Office 365. In this case a P plan (no Dirsync, Federation or such), you can see the result in the screenshot:
Funny thing is that if you try Add-MailboxPermission to add Send-As permission, the error message redirect you to Add-ADPermission.
For handing out Send-As permissions (and other rights) in Office 365, you’ll have to use Add-RecipientPermission. And cmdlet does not work in a On-Premise Exchange environment 
Also see: Office 365 Help Give Users Send As Permission
I'm an employee at a Dutch IT-Company (www.ogd.nl) and frequently come in contact with customers with specific questions on Microsoft products. Of those products my personal favorite is Microsoft Exchange.
Sander made me aware of the DirTeam.com/ActiveDir.org blogs.