1. What MTA are you using? Postfix or Qmail?
2. Show the output of /usr/local/psa/bin/grey_listing --info-server
3. Try the KB "How to recreate mail handlers in Parallels Plesk Panel 10.4 and above" http://kb.parallels.com/en/113664
4. If it did not resolve the issue attach mail logs