Evolution uses a special .csv format while it imports contacts. The problem is that there is no description how to make that .csv. Since I couldn't find the "Export contacts to see what damned .csv format do you use"-button, I asked a good friend of mine, Google.
The whole thing is much simplier than we think:
$ cd /usr/libexec/evolution/2.6
$ ./evolution-addressbook-export --format=csv > /home/me/Documents/contacts.csv
Voilá.
We have now our existing contacts in the special .csv format Evolution likes.
Now we could edit it with Excel or with OpenCalc, and fill it with your tons of e-mail addresses.
Save and, import it into Evolution.
Enjoy.
I attached an empty Evolution-like .csv to avoid grey hair.