Figured it out and thought I should share what I found, though it is likely related to custom code on our site.
For some reason, the Auth0 ID that was returned to the WP site was not being captured properly. What is odd is that this only happened about 50% of the time, and started without any obvious triggering change (no changes to WP code in particular).
So Auth0 would send someone back to the site after logging in, but Wordpress could not connect the user to an account and would try to create a new one. Of course, WP would see that a user already existed with that information and would throw the error.
This problem was with custom code created using the Auth0 API. Still not sure why it would work sometimes and not others, and what changed to start the problem. We fixed it by adding an additional layer of checking to handling that value.
If you are running into this problem, check the auth0_id and auth0_obj items for the affected users in the usermeta table. If the auth0_id value is empty, that’s your problem. You can fix it on a case-by-case basis by looking up the users’ ID in Auth0, but to fix the problem you’ll have to figure out why that value isn’t being captured.
Just to be clear, this all applies to the Auth0 Wordpress plugin. If you’re not using that plugin, you likely won’t have or need those user_meta values. Also, to be clear, those user_meta values have the prefix of your WP tables – so by default would be ‘wp_auth0_id,’ and ‘wp_auth0_obj.’