@vincenzo1967
Io ce l'ho configurato come te e non ho alcun problema. Gmail ha questo di bello che usi il suo server smtp.
Sicura che la password sia giusta? prova a rimetterla non si sa mai.
Riguardo ad alice invece prova ad usare il server smtp della tua linea wifi (telecom, fastweb ecc). Credo il problema possa essere quello.
@Commodore
Credo che tu possa recuperare il tutto dal web. Se è pop3 ed hai messo il flag su "mantieni elementi sul server" sei a posto, altrimenti non puoi ripristinarli. Ma è un problema legato al protocollo pop3, non del S4 o di android. Se avessi configurato l'imap allora avresti potuto farlo.