Messaging module maintains a table called messaging_destination, which it uses to send emails to subscribers. That works fine until a user changes his email address in the user table.
It appears that there is no mechanism to update messaging_destination to pick up the changes. The only way I can see this occurring now is to delete the user's subscriptions and recreate them, which is an administrator's nightmare.
This probably should be dealt with by updating the messaging_destination table during cron runs.