"Have you checked to be sure that you didn't disable these E-mails on the options tab in WP?"
Of course! And no, that wasn't the problem (at least in my case).
I did, however, just discover a way to get around the problem. Since apparently my problem had something to do with the smtp server rejecting messages, I installed the WordPress Swift SMTP Plugin and configured it to send through the server via authenticated means. The reply-to section of the received e-mail messages is a bit odd in that it includes both the sender (wordpress@whatever.com) and the commenter's e-mail addresses, but at least it's functional.
Also, when I enabled it, configured it, and tried the built-in test e-mail function, it's worth noting that my test e-mail did NOT send (although it said it did). I still receive comment notifications, though. Weird.