This issue applies accross Outlook 2007 on Vista and XP, and also affects Plesk 7.5x
Basically there is a bug (or there has been a change in the way outlook works) the prevents 2007 from doing authenticated smtp with the version of qmail installed (the issue is not Plesk specifically - if you do a google serach you'll find a few moans about various isps including COX but no solutions, and I doubt COX is using Plesk for all its emails?).
The work-around is to ask clients to put a tick on the receive before sending tick box in Outlook, and to enable pop-before relay in Plesk. Not all of us are happy with this workaround obviously.
What is interesting is that nothing appears in the maillog when trying to send (when getting the errors).
This is very very bad.
I believe this is an issue Microsoft will have to deal with, and not Plesk, given that all other clients work fine with qmail (with the exception of Entourage for the Mac, but I understand that's an Entourage bug).
Incidentally all clients affected have been using Norton AV, and all my tests have been done with Norton Internet Security installed so I suppose there is a small chance the issue is related to that and not outlook 2007. I doubt it though.
Faris.