We also ran into issues with using the Okta OAuth/OIDC integration with Teleport and ended up using SAML [0]. Perhaps more painful, especially if you are more familiar OAuth/OIDC but it worked. This was when Okta OAuth/OIDC was still in beta so perhaps it has improved since then.

[0] https://developer.okta.com/authentication-guide/saml-login/ ; https://gravitational.com/teleport/docs/ssh_okta/