I suggest you to go to Site administration > Development > Debugging and then you should choose the following:
Debug messages: DEVELOPER: extra Moodle debug messages for developers
Display debug messages: Checked (Yes)
Debug email sending: Checked (Yes)
Then try to send messages with Users > Accounts > Bulk user actions
There you should choose some users and "With selected users.." -> "Send a message."
Then you should see a list of debug errors you could attach it here to see where the error is.