Yo hago lo mismo que telepunky: mis contactos todos bien organizados en Gmail y desde ahí se sincronizan con la Magic; y, aparte, copia de seguridad CSV en el disco duro por si acaso...
M_Cobretti, a lo mejor lo que te pasaba es que borrabas los contactos de Gmail y luego se te borraban del móvil para estar siempre sincronizado, ¿puede ser?