Se Vodafone ha una restrizione su altri provider non ci puoi fare niente.
E' successo anche a me con l'account tin.it quando passai a Infostrada ... nada posta.
Da allora uso solo accounts "free" (gmail, yahoo ... ecc) che li scarichi a prescindere dalla connessione.
Se ti può essere valida come soluzione, fai un accont gmail e gli fai recuperare l'account Tiscali.