After adding Send As rights in the Office365 Exchange portal, do not expect that Outlook will work with these permissions automatically.
It needs time to propagate changes and download fresh copy of Offline Address Book.
You can try to speed up the process by:
1.Deleting old entry of address from the FROM field in Outlook (delete auto-complete hint)
2.Getting fresh copy of OAB (Outlook, Send/Receive, Send/Receive groups, Import address book)
3.Wait...and try again if it does not work. Remember it could take 24-72 hours to propagate changes in OAB