I have loads of strangers in my address book. I guess I have e-mailed them one time or another (update: I have). The option for automatically adding people to my address book is disabled. Odd.
It was a bug in previous version of Evolution, your version has this fixed. You probably noticed, it doesn't add new contacts anymore. The new Evolution cannot delete your contacts, because it cannot distinguish between contacts you added there yourself and those automatically added by mistake. See upstream bug [1] for more details. [1] http://bugzilla.gnome.org/show_bug.cgi?id=491062