In Moodle 2 a lot of the notifications controls have been merged together into something called "Messaging", so a user can access "My Profile Settings" -> "Messaging" and have full control over how they receive these "messages" from the system.
There is also a system, also called "Messaging" that allows people to send messages to each other. This can be turned on/off in "Advanced Settings" with the following option:
name: Enable messaging system
With just those settings there's scope for confusion between these two "Messaging" systems. It is made very slightly clearer by the help ("Should the messaging system between site users be enabled?") but I'm guessing that text was written before Moodle had 2 "Messaging" systems.
This messaging system is referred to (I assume) in the last entry of the "Messaging" preferences, where it says: "Prevent non-contacts from messaging me [x]" under the heading of "General Settings" which implies the two systems have merged.
As a final confusion, you can go into the participants list of a course, tick a checkbox next to some user names and then select the option "Send a Message" to send a message.
This isn't turned off by the previously noted "Enable Messaging System" option, nor is it obviously controlled by the "Messaging" options in your profile. I'd quite like to be able to turn this off, as we already have systems for contacting students (individually or en masse) and this duplication leads to confusion. But so far I can't find any way to disable this feature.