Stavo cercando anche io una soluzione al problema... e forse l'ho trovata: se connesso via wifi il server Tiscali viene bloccato, se connesso via 3G non ci sono problemi.
SE Xperia X8 + Android 1.6 + K9
In ogni caso, se configuri su K9 il server POP3 lasciando una copia dei messaggi sul server (magari fai una prova ad hoc su un account nuovo) dovresti ottenere lo stesso risultato senza avere il blocco del server.