No Comment / Admin Notifications, PHP Mail is enabled

Hi there. I know there have been countless threads, but none seem to match my issue. Starting in late June, I stopped receiving comment notification, new user notifications, etc.

Now, I have 2 WordPress blogs and 1 PHPBB message board on my domain (ickmusic.com), and I stopped receiving any sort of notifications for all of them at the same time. This obviously pointed to the web server (and still does), so I had my host make sure that PHP Mail is enabled on my server. They say it is/was.

Does anyone have any tips on where to go next? I try to keep working with my host, but honestly, every time I reply to them, they seem to get more confused, and ask me for the specific steps to reproduce the issue. *sigh* I respect our counterparts in India, but the communication gap is extremely wide.

It still has to be something on my host/server side, right?

Any help in resolving this would be appreciated. (by the way, I have checked and double checked that all settings in wp-admin are correct.)

Pete