Did you ever find a solution to this problem?
One of our Moodle sites has also developed this problem, but only when messages are posted by one of our two site administrators.
The email addresses for both the poster and postees are OK and have been working well until a week or so ago.