Registration problem - MyBB rejects everyone as spammers

[Booher]

AdminCP => Configuration => User Registration and Profile Options => Display a hidden CAPTCHA => No

That should fix your problem.

Can you please help me understand why this happens? What is the feature "supposed" to do, and why isn't it working for every user who tries to log in?

It creates a hidden field that should be empty, and most spam bots will fill it in. I'm assuming it was conflicting with another plugin of yours in some way.