What do you mean by "federated"? I've heard XMPP described as that but never really seen it explained.

The impression I've gotten is that somehow users on one XMPP network could chat with users on another? So if Google and Facebook still both fully embraced it, a GChat user could message a FB user without anything extra?

That's exactly it, except each of them is not an XMPP network but just a single domain (there's only a single authority, so it doesn't make a lot of sense to talk of network). XMPP works exactly like SMTP in this regard: you can send a mail from [email protected] to [email protected] just like you can (could, at least) send an XMPP message from [email protected] to [email protected]

Was this ever implemented anywhere like this? XMPP can do anything in theory, I understand, but had this ever worked? How bad was spam in this case?

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).