I'm the original poster above. As a footnote to this story we decided to go with Duo Security as our second factor on OWA and in other situations. We love and will continue to use Okta for SAML but will use Duo as our second factor instead of Okta Verify for all two-factor needs within Okta due to a rich integration between the two offerings. In addition, Duo offers a rich and well supported integration for OWA and Microsoft Remote Desktop Services/Farm, both of which we use, in addition to many other integrations Duo offers.
We found this to be preferable to implementing WS-FED and doing two-factor through Okta, and most likely paying Okta professional services to do it due to lack of documentation around OWA / WS-FED integration on Okta's part. Okta PS seemed to be able to easily handle OWA but did not seem to be have much experience around the Microsoft RDS deployment that we wanted to have two-factor authenticated as well. I would have loved to only deal with Okta on all of this, however Duo had a better story with the "on-prem" apps that we had to handle.