You can "message" anyone you want, except that if you aren't friends it will almost always fall in some weird secret hidden bucket that most people never look at, and is hard to find even if you try. If you share a direct connection it might go through, but in my experience not always.