There seems to be a conflict between older versions of Kitten’s Spaminator and WP1.5 comments. Disable the Spaminator and things clear up – or at least they did for me.
I’m now on 1.2.2 and still have the same problem, using the latest version of wp-comments-post.php (which I assume is the file responsible for posting notifications).
I’ve treble-checked my settings, and they are all correct.
Additional information:
I have Kitten’s Spaminator installed, but disabling the plugin doesn’t help. I’m using WP 1.2.1