I have a personal Office 365 account. My email is firstname.lastname@example.org. My main email address is email@example.com (Yahoo). I have added this other account everywhere I think I should: aliases (and made it primary), 'Sync Email' at Outlook.com and made it my default From address. Retrieving email works ok. In Settings, the default From drop down I can also see firstname.lastname@example.org - no idea where this came from and I can't delete it. It doesn't show up in aliases.
When I send an email from the @otherprovider.com email the recipient sees Display Name <email@example.com> on behalf of Display Name <firstname.lastname@example.org>
This is the expected behavior, messages sent from Connected account will always be "sent on behalf of". As for changing that outlook.com alias, you should be able to do so in your settings. It's sort of your "primary" email address now that Hotmail is no more.