Buenos dias!!
Dos cosas, la primera, si has liberado el terminal por IMEI, creo que aunque hagas un Factory Reset, no quitas la liberacion, porque el Factory solo toca lo relativo al Firmware, no al resto de cosas que controlan el Hardware.
La segunda, has probado a borrar datos en Menu > Aplicaciones > Administrar Aplicaciones > Todas > Market?? Creo que con eso tambien debería valer, y ya despues, borrar su cuenta de Sincronizar y del propio Market, si no lo ha hecho ya solo al borrar los datos del Market.
Saludos!!