Turns out I hadn't exactly fixed the problem. If I did, it was only partially.
Microsoft thought wise of blacklisting us, while
no one else has (
see yourself). I'm rather pissed at them, because I bet it's because our domain name has the word "hack" in it; oh noes. This is a dedicated server, so I don't see how someone could've used it to spam e-mails.
Basically this prevented the server from sending any email to hotmail/msn/live/outlook/etc.
One option not so available was convincing M$ to take us off from the blacklist... An apparently extremely tedious process, and they're assholes about too.
In any case, I have finally fixed the problem by configuring the forum to use gmail's SMTP, but sadly I reached the daily limit of ~150 emails that I can send per day. So if you receive any PM today or anything, you won't get any e-mail notification. Likewise, it won't be possible to start and complete registering today. Said e-mails will be queued and delivered tomorrow. I can always provide some assistance if you join IRC.
I apologize for the inconvenience. Blame M$.