Google’s response to the Poodle email vulnerability seems to be to send using TLS where the server is properly configured, but queue messages where it isn’t. So to enable email receipt we need to tell qmail SMTP which encryption to use, and provide it with a valid certificate.

Plesk supports SSL certificates, obviously, but also has a self-certified certificate for use with the control panel. This can be used for SMTP.

Either for qmail:
cp /usr/local/psa/admin/conf/httpsd.pem /var/qmail/control/servercert.pem
or Postfix:
cp /usr/local/psa/admin/conf/httpsd.pem /etc/postfix/postfix_default.pem

IMAP:
cp /usr/local/psa/admin/conf/httpsd.pem /usr/share/imapd.pem
POP3:
cp /usr/local/psa/admin/conf/httpsd.pem /usr/share/pop3d.pem

And to make sure the certificate is used, create the TLS cipher rule files:
openssl ciphers > /var/qmail/control/tlsserverciphers
openssl ciphers > /var/qmail/control/tlsclientciphers

(servercert.pem tlsserverciphers and tlsclientciphers were all empty in my installation)

It may also be worth checking the integrity of the qmail installation:
/usr/local/psa/admin/sbin/mchk