We pass through the contact book to see if a user exists there, we return them back as a connection. If not we return them as someone you can invite.
Do you log who someone has looked up in Circles when they join? If you do then you could trivially reconstruct someone's contact book.
That's what Facebook were found to be doing, except they were actually creating 'shadow profiles' for the contacts.