Always the simple things...
So for the last hour, I've been trying to get Microsoft Messenger:mac working with the Office Communications Server. I try using my credentials, and the only error I was getting back was "sign in to Microsoft Messenger failed because the service is not available".
So I busted open WireShark and had a look. It was constantly getting a 200 (OK) back, right before Messenger threw the error. I tried turning off my firewall (10.5 has it's issues...), and it still won't work. I try manually setting the server settings, nothing. So I head over to the Microsoft page, to see if I had an outdated version. And that's where I saw it...
Turns out, Microsoft Messenger:mac won't work with Office Communications Server 2005, only 2007. WTF!?!?! C'mon Microsoft, why won't you let your client connect to your own server, just because it's a little outdated!!!! Anyway, the moral of the story: If you get this error, just downgrade to version 6. It works as expected