Gelöst...
Ich habe nun endlich die Lösung gefunden: Ich hatte im Internet in Windows Live alle Kontakte aus Outlook abgespeichert. Diese syncronisieren sich zusammen mit meinen Mails etc. über GPRS auf mein Handy, was ja eigentlich eine wunderbare Funktion ist - quasi ein Push-Adressbuch. Dummerweise hatte ich am S710 den Knopf "Dubletten zusammenführen" (oder so ähnlich) nicht aktiviert, weshalb plötzlich alle Kontakte doppelt da waren.
Vielen Dank euch aber dennoch für eure Hilfe...