Another thing we might consider is making it a little backwards -- when someone submits their address book, they already have an account. We can make it so that a user can select a privacy setting of "when someone submits my email, notify me, but don't tell them".

I was trying to think of a way to word this but gave up, but yes. If I search and don't find people that can be frustrating, but if they get notified I found them and can them come get me if they want to, that can help.