We are doing an Office 365 pilot using shared domains/internal relay following Microsoft's instructions here: https://support.office.com/en-us/article/Pilot-Office-365-with-a-few-email-addresses-on-your-custom-domain-39cee536-6a03-40cf-b9c1-f301bb6001d7
Currently we have internal relay set up and our on-premises Exchange server is forwarding for a couple users, e.g. firstname.lastname@example.org forwards to email@example.com and appears to Bob as if he received it at firstname.lastname@example.org. However, when Bob replies to emails, his recipients are getting it from email@example.com. Since we've set up SPF, there shouldn't be a spam issue sending as the domain.
We've tried setting Email Address Format in Email Address Policy, but it shows as "unapplied" and seems to have no affect.
We've also done everything we can to complete setup except actually change the MX record, which we can't do.
How can we configure Office 365 to send emails on behalf of @company.com?