Yesterday SOME notifications were finally sent. After 8 hours (!!) of delay some "notificationSent" values in ow_mailbox_conversation have finally changed from "0" to "1" and notifications were sent. But some are still sitting with "0" value.

I cannot figure out how it works.

oxwall does everything on on cron 

when u add lots plugins and have plenty members ots to much for one cron

the cron needs to be 2 or even 3 differant runs

every script does this because of problems like this

but not oxwall

skatdate has 2 cron runs to fix this problem 

Notifications about new message are sent by cron

Which option have you set in your notification settings? 

Immediately

Automatically (if you don't show up on the site for 2 days)

Never

Before the notifications being sent it appears in the ow_base_mail table then if the cron runs and configured properly the table empties out and the mails are sent to your mails server. 

So you need to make sure your cron is properly configured and running. You can send test mass mail and check whether the mail appears in the ow_base_mail table and then goes out from there. As soon as the table empties out, the software is no longer responsible for the mail to be delivered, the rest is up to the mail server. 

It doesn't happen all the time, but occasionally.
I DID try sending test mass-mail to our three moderators, and the mail appears in ow_base_mail table right away, then leaves it as cron runs (once a minute), so my cron is working. 
Probably Tammy is right, the software is lagging, but I only have 22K members. And what will happen when I have 100K??? 500K?? :)