I'm not familiar with Fedora however mail queue is usually stored in /var/spool. For example, on exim based cPanel servers I just delete all the directories in /var/spool/exim, then restart exim and it re-creates what's needed and runs fresh from there.
What mail server software are you running? If you are using a stock Fedora install with no control panel, then it is probably sendmail.
To flush the mail queue in sendmail:
/sbin/service sendmail stop
rm -rf /var/spool/mqueue/*
/sbin/service sendmail start
That should clear out all of the messages in the sendmail queue.
Correct, Horde is just a webmail interface, that connects to any MTA software.
It would appear that plesk 8 uses the QMail MTA, and that plesk 8 has an interface built into it to clear the message queue.
I do not have a plesk 8 install handy to check, but look in there.
You could also log into the server via SSH, stop the qmail service, remove the qmail queue by hand, then restart the qmail service.