I'm okay with basic per-IP or so rate limiting, although it would be great if systems could do better and be able to limit differently based on different criteria, such as whether the target login exists or not, or is different from the last attempt, or both.

I'm not sure such a suggestion relates to a reasonable threat model. I guess that depends on attacker behaviour, and I don't know enough about that. But it wouldn't be crazy for a scanner to have thousands of source IP addresses, either due to IPv6 or just by being part of a botnet.

"Different from the last attempt" is very much an "arms race" situation. Well, so's changing the port number, and I do it too (it's not totally pointless; it reduces log-spam, anyway). But if it became common, it'd be so easy to alternate between attacking the "alice" and "bob" accounts.

That raises the question of why every server is expected to implement stuff like this. A library could be useful. (I don't think socket activation is the solution; spawning processes on request makes the CPU hit worse, and the memory usage less predictable.)

if you don't put in rate-limits, you're donating CPU cycles and RAM to them

That's probably worth quantification. You've already donated CPU cycles and RAM by receiving their packets. Is the extra "donation" of processing their request actually significant? (Has anyone measured?) If so, I wonder whether re-working the authentication would make sense. Standards-compliance may preclude that; but, hypothetically, protocols could be defined such that clients need to do the bulk of the work, maybe even including some kind of proof of work. (Although, again, a thousand-machine botnet might not have as much trouble as we'd like.)

you require MFA after basic password authentication succeeds

Ask for the MFA code first?

Without rate-limits, these programs have very little limits on their blind behavior; with rate limits, you can either slow them down (perhaps drastically) or maybe even provoke error messages that get the person's attention.

To me, that's quite a different goal, and the best solution might be very different. With IMAP, for example, I might be inclined to accept logins on non-configured accounts that are getting hammered, and "deliver" a message describing the situation. Maybe there'd still be rate-limiting to save server resources; then again, if it's cheap for the server, giving a client a "new" message every time they connect will probably get a mis-configuration fixed really quickly.

When the threat is mostly limiting annoyance, then the efforts may not need to be fully effective. If the attacker uses a single IP limiting is simple and effective. If they use several IPs but single account it is still simple and effective. With large amount of IPs and accounts the limiting can remain simple but is much less effective, but it is probably still much more effective than the attack. Thousand IPs and hundred attempts before severe limits make that attack worthless, and at that scale the biggest harm are the log entries.

About the IMAP and "delivering message". I think nowadays the consensus is that a service shouldn't give any indication whether the account is right of wrong, all failed attempts should receive the same "wrong password", whether it really was wrong, the account doesn't exist or it's expired or otherwise disabled.

The question I've often wondered is what style of rate limiting to use. I would probably prefer a tiny but exponentially growing delay. Second attempt has a 10 millisecond delay, 20 is at 1 second, after 30 10 seconds, 40 and 100 and so on. A human won't have even noticed the delay by the 30th attempt when they give up. At work the rate limit used to be 30 minute account lockout after 10 failed attempts, which could be a real annoyance. Forget to change the mail password for your cellphone and you would be randomly unable to login to your computer.

About the IMAP and "delivering message". I think nowadays the consensus is that a service shouldn't give any indication whether the account is right of wrong, all failed attempts should receive the same "wrong password", whether it really was wrong, the account doesn't exist or it's expired or otherwise disabled.

I also get the impression that's considered a "best practice" for authentication. Probably the message would be more like "authentication failed" than "wrong password".

It's just that, for IMAP, there's a good chance the SMTP server will tell people whether an account exists. The IMAP login names usually match the SMTP local-parts, except for aliases.