This is the most obvious explanation. It compares your email to the list of contacts that other people have imported. If you were on their list, you may 'know' them. Pretty simple.
Not necessarily. I've had recommendations from people I've never exchanged emails or phone numbers with and our only "connection" has been through Facebook or Twitter. They'd have no reason or way to have me in their contacts list. As the article describes, they've even recommended people who just happen to share the same name as someone I DO know, but otherwise have not the slightest connection in the world with.
Simpler explanation: Random services where people signed allowing 'share data with third parties'. That's not random wording, those precisely are this type of metadata sharing agreement where money exchanges hand buying people information.