If you're using Gmail then your notification emails may simply end up in the spam order - since a year or so ago, they seem to trigger the spam criteria in the Google system. I've retrieved one of the emails, sent a reply email to the stated adress to whitelist it, and ever since I'm receiving my PM notifications again.
Under Profile/Settings, note that "notification" refers to emails, not highlighting recent posts.