Last week, one user (from Poland) had got big problem with sending mail under Moodle (thread: http://moodle.org/mod/forum/discuss.php?d=12924 - only in Polish, sorry ).
When I was trying solve this problem, I've found that Phpmailer library 1.70 (which is part of Moodle 1.4.1 and earlier) has serious bug which appears during authorization process to some MTAs (it's impossible to send mail from Moodle via such MTA).
The solution is very simple - administrators of Moodle sites should upgrade Phpmailer library (which is localized in Moodle at folder: "moodle_folder"/lib/phpmailer) to newest 1.72 version of Phpmailer.
It can be download from page http://sourceforge.net/project/showfiles.php?group_id=26031.
I suggest to upgrade Phpmailer library in official Moodle package