So far my two favorite campaigns, one I am currently in, started with the PCs knowing each other and having some common bond.
In my favorite we started with just two characters, you can of course easily adjust this. It was 2nd ed and I was playing a Swashbuckler who was a prince that didn't want to be one and the other player was his best friend and companion. They ran off together from their island nation to explore the mainland. This game lasted I believe over 2 years of game time and about 4-5 years of real time.
The campaign we are in now the DM chose a small town for us to start in, gave us all the details, then asked us to create characters and place them in this setting with the only requirement being that we have ties to the town, that we have a reason to care about its well being. We could talk with other players and integrate our character backgrounds as we saw fit. (You can see how this worked by reading our story hour, link in the sig.)
I have to say the key to both of these to me was that the PCs knew and cared for each other or a common bond (and so eventually came to care for each other). I like these themes much better than just happenstance throwing characters, who may hate each other, together.