Basically all public XMPP/Jabber servers implement this, and it is fairly easy to set up (multiple of my contacts run their private servers). Spam has never been an issue for me.

Google used to implement this, DDG still implements this, most small->medium XMPP servers still implement this. For a while, Facebook was the odd one out for not supporting it.

Spam was less of a problem than e.g. spam on AIM. There's the fact that it's not any harder to sign up for AIM than a XMPP network, it's not popular enough and the audience too tech-savvy for spammers to bother, and if a specific host was a bad apple it's easy to BL them.

This part is actually the one that is in the core of XMPP, so it doesn't work in theory, it just works everywhere (as long as administrators have allowed federation, of course).