"Then when SAML is re-enabled, edit the each users profile and set SAML2Authenticate Only to unchecked"
For some reason this doesn't seem to be necessary, at least not in our case (could also be a by-product of very old installation; I think the original version was 7.1.5). All that matters is that a password is locally set.
@timo: just as @SuiteCRM explained, each user needs to have a password set in the SuiteCRM's own authentication mechanism. Once set, the user should use that password when logging in with the Outlook plugin.
I'm having the same problem with plugin version 3.0.22 and SuiteCRM 7.11.8. The relationships seem to be ok in studio, but the module does not show in the plugin's list of custom modules. Rebuilding relationships didn't also help.