En principio es correcto lo que te han dicho los de vodafone.
Aunque los jodios suelen omitir los 0 de la izquierda, si el codigo de desbloqueo por ejemplo de desbloqueo los lleva si es 01233445676 ellos solo te diran 1233445676. Siempre suele ser la misma cifra de numeros el codigo y los que faltes se rellena al inicio de este con ceros (lo que no se cual es la cantidad de cifras).
Lo que es raro es que no pida ese codigo al arrancar con una SIM de otra compañia ajena a la que esta programado el terminal.
Si a alguien no se le ocurre otra idea o el motivo de eso, puedes probar poniendo por Odin otra ROM por si fuera un error de software. La duda es poner otra de vodafone o una libre.
Supongo que casi seria mejor esta ultima pero no tengo ni idea, es la primera vez que leo este fallo en un telefono y he enredado mucho por foros de distintas marcas (Nokia con y sin symbian, motorola sin SO, sony sin SO, HTC con window y android, palm, panasonic sin SO, etc, etc, etc...)