Yes, I followed the perfect server guide and yes I already ran the update.php this morning to try again and no, it didn't fix it.
I managed to isolate the problem to postfix not using sasl properly. When connecting to the smtp port it's not using authentication at all.
Code:
$ telnet website.com 25
Trying X.X.X.X...
Connected to website.com.
Escape character is '^]'.
220 ns1.website.com ESMTP Postfix
helo website.com
250 ns1.website.com
exit
502 5.5.2 Error: command not recognized
quit
221 2.0.0 Bye