I have the same problem
I have the same problem and my server is not an open relay
It's a Postfix 2.8.7 compiled on Fedora 16
Cyrus SASL (2.1.25) authentication is enabled with method PLAIN
Users are on a MySQL DB hosted in another server.
Only ports 25, 53 and 22 are opened.
220 myserver.mydomain.com ESMTP Postfix