PS DreamHost is fine, I've been using it for more than a year now to host my main blog, based on WordPress, and I didn't have any serious problems up to now. The problem with the email notifications occured right after my last WP upgrade, so I guess, it's not a hosting problm, but rather a WP problem...
Actually it probably was (still is) dreamhost's problem. They sent me a mass email (which is infuriating after 3 days of me asking for help and not hearing from them) saying their server wasn't executing mailscripts for the last few days. That the system had been "clogged up" and things should be peachy now. Well they aren't- I'm starting to get email notifications from 3 days ago, but only some.
But here's the solution that fixed all this for me:
I was in contact with several people who work at WP and one of them suggested doing this:
2. then install this plug-in:
3. in the plug-in options tab set the options to:
send mail using SMTP,
send the mail using your new email address,
fill in the SMTP host, username and password that your host gave you when you set up the new email address,
YES, use smtp authentication
4. Send yourself a test mail using the plugin to make sure it works.
By doing all this you are bypassing php mailscripts altogether and you don't have to rely on your host having them working.
It worked for me, I tested commenting on the blog and it came through immediately. When I turn this plugin off and try it I'm STILL not getting email notifications.
Hope this helps, good luck everyone.