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.
$ telnet website.com 25
Connected to website.com.
Escape character is '^]'.
220 ns1.website.com ESMTP Postfix
502 5.5.2 Error: command not recognized
221 2.0.0 Bye