My story: I had the same issue on fresh Ubuntu+Plesk. I could not find the cause and finally get broke Postfix :)
My resolve path:
1. Tools&Settings -> Plesk -> Updates: Uninstall Postfix by installing Qmail, then install Postfix by uninstalling Qmail
2. Tools&Settings -> Mail -> Mail Server...