That would make sense, but the button disappears even when the option to allow messages is enabled.
Setting the Hide my public profile and presence features seems to always remove the Message button from the user cards, regardless of whether the user can be messaged.