Si tus cuentas son de GMAIL y/o HOTMAIL puedes añadirlas como Exchange con los servidores m.hotmail.com y m.google.com con lo que además de recibir los mails del rollo "push" o sea, inmediatamente quizá te ayude en los problemas de configuración que tienes.
Sobre la red desde luego es muy raro, yo llamaría a tu operador y que te guien en la información que corresponde a tu tarifa de datos.