I've been trying to get this working for so long it's crazy.
Finally, using the amazing wp-mail-smtp plugin (http://wordpress.org/extend/plugins/wp-mail-smtp/) to send the mails from smtp works 100% perfectly with wordpress 3.0.1
I heavily de-bugged the comment-reply-notification and discovered it's 100% fine, no need for ANY modifications at all.
(You can even use google to send the smtp mails - see here: http://www.callum-macdonald.com/code/wp-mail-smtp/)
I hope this helps someone!