We've been using addresses to send messages for a long time but Facebook has made them obsolete. Our "identity" is our new address. We don't need e-mail addresses, phone numbers, or IM handles anymore but address books, strangely, might still be useful.
Addresses sprang from the need of identifying someone within a crowd without a central directory. Before addresses, we didn't have the crowd or the central directory. In 1229 King Frederick II wrote a letter to King Henry III of England updating Henry about the latest news. When Frederick wrote that letter he probably just put Henry's name on an envelope, stamped it with wax, and then told a servant to deliver the message. Frederick didn't need an address because there wasn't a crowd - there weren't many people he could send a message to.
The first widespread use of addresses in the US came about in 1775 when Benjamin Franklin formed the US Postal Service. Sending letters was brought to the masses and a system was standardized to move these sheets of paper around. You couldn't just write a person's name on an envelope anymore because the number of recipients went way up. The possible number of recipients went up because it became cheaper (and just plain possible physically) through the use of technology like trucks and roads to send a letter to anyone.
Good old Frederick probably didn't have an address book but the first US citizens needed them because although they could remember who their friends were like the kings, they couldn't remember all those addresses. The old kings didn't need them since in their day addresses were the same thing as identity.
With mailing addresses, your identity is still pretty close to your address since one is contained in the other. But once e-mail arrived "address" and "identity" fully separated for the first time. For once, a person could choose whether to reveal their identity as part of an address. I could choose to make my e-mail email@example.com or firstname.lastname@example.org for example, and still receive messages just the same either way.
Finally, jump to current day. Facebook comes along and makes the old new again. Let's assume for a moment that Facebook reaches its goal of making everyone on the planet a user. Coupled with an excellent, graph-weighted people search (which it has) your identity ends up being your address again, just like with the medieval kings. Meaning, all you really have to know is someone's name to send them a message.
Wait a second, what? So we're now all kings like Frederick where we can just scribble a name on a sheet of paper and hand that to our servant and trust it gets to the right person? Yes, essentially. Facebook is our servant and its almost perfect mapping of real people to accounts provides the infrastructure necessary to make this possible.
Facebook messaging is a departure from e-mail precisely because it ties so strongly "identity" with messages and abandons "addresses". Facebook actively bans fake accounts, while Hotmail allows you to create as many as you'd like.
If all it takes to message someone is their name, then it follows that the only people you can't message are people whose names you don't know. You know Barack Obama's name, and you can message him if he has his Facebook privacy settings at their default. OK, so famous people will likely want to alter their privacy settings, but for everyone else the rule still holds.
But wait, you might say, what about the fact that you aren't friends with everyone on Facebook. Facebook lets you talk with your friends and since I'm not friends with everybody that's the real reason I can't message the President. It turns out Facebook's default privacy settings do allow you to message non-friends, they just restrict you from seeing personal things like photos you're tagged in and your email address and phone.
You can message John Smith too. I know he has a common name and it'd be more helpful to have his address. But it's likely you met John Smith at a party, or a conference, or some real world event with real world relationships that Facebook knows about explicitly or implicitly and those allow him to pop up in that spiffy search right away.
What about those pesky address books, things people hated anyways. Kings didn't need them, Benjamin Franklin and friends did, and since we're back to the "king situation" people on Facebook today don't need them again.
Well, not quite. Address books just look much different. It's no longer a list of addresses. Rather, it changes to become a list of names. Your only task becomes remembering the names of people and how they are relevant to you rather than managing the addresses associated with them (or managing phone numbers which are just another type of address). You could try to just keep this list of names in your heads, but we meet so many people these days that's just not possible.
And Facebook is definitely not good at this either. It only remembers a small subset of the people you'd really want in a modern address book. Which means Facebook can't be the end-all and be-all of our social world forever. Which is a good thing for Google, Apple, and all the startups and would-be startups just getting started.
Thanks to Kartik L. and Andrew O. for providing feedback on this post.