I think the "An account with your email address could not be found" message might be misleading.
Is Prevent account creation when authenticating enabled on Site administration → Plugins → Authentication → Manage authentication?
If it is this option preventing logins, I fairly sure this behaviour hasn't changed since Moodle 3.8.