PM notifications sent only sometimes

On my site the notifications are only being sent out intermittently. I've looked through the faq and the settings in the backend are correct, the email notifications are enabled, I'm using phpMail with a valid email address, and I'm assuming that it is working since the emails are sent out sometimes. I've checked my spam filter and haven't seen any of the notifications. We have less that 60 users on our site so I doubt that the system is getting overwhelmed.

I'm at a loss, what should I look for next?

Thank you!
-Laurie

Although I don't want to, I'm starting to look for an alternative because my users consider the notifications essential.

Any last suggestions?
Thanks!
-Laurie

You could also check if your server is backlisted and emails are dropped as spam. It is also possible that your MTA is not configured correctly. There are several possibilities.

uddeIM notification are working fine on Joomlapolis with over 300.000 users and thousands of other sites so your tiny site should be no problem at all.