When diagnosing mail problems it is always best to inspect the mail logs first, they can be found in the following locations:


Linux

/usr/local/psa/var/log/

The log files are called "maillog" for the currently active log file and "maillog.processed" for older log history.


Windows

C:\Program Files (x86)\Parallels\Plesk\Mail Servers\Mail Enable\Logging

Note: The above is for the location on a 64bit OS, 32bit will not have (x86) after Program Files. 

The logs are stored in further directories, "SMTP" is for SMTP traffic and "POP" is for all POP traffic, it is usually the SMTP logs to check.