According to Facebook’s current messaging policies, all users should be capable of receiving messages. However, when viewing some profiles, belonging to Friends of Friends or non-Friends, while logged in with my account, the "Message" button is missing. Also, mail sent to such users' Facebook email addresses bounces back. My account has not been blocked by these users.
In the case when you are NOT fb friends already, it will depend on the privacy setting of the profile owner. E.g. they can make their profile searchable/non-searchable, and in case of searchable, they can also set if they will allow strangers to message them. My profile is set up in this way, so if people want to be friends and they know me, they can just message me to indicate the interest.
Previously, users had an option in privacy settings to control who could send them a message. Facebook is rolling out a change that will allow messages to be sent to everyone, although if the message is not from a friend the message may go into the "Other" section of messages and no notification may be received (unless the sender pays a fee of $1 to $100). If you are attempting to send a message to someone that does not yet have this change and they have previously restricted this privacy setting then the Message option may not be available.