Lo primero que debes tener claro es si la cuenta de GMAIL la configuraste MANUALMENTE o con el ASISTENTE que tiene OUTLOOK. (también debes concretar si es una cuenta personal de GMAIL o es una cuenta WORKSPACE de alguna institución)
Si la configuraste con el ASISTENTE no deberías de tener problemas (yo he configurado muchas y sin problemas). Si has hecho la configuración MANUAL, pues debes comprobar en la web de GMAIL, en los AJUSTES, que tengas permisos de terceras apps, para poder configurar, ....
Así por encima, más o menos...
POP3:
Si utilizas GMAIL
Descarga el correo en OUTLOOK y deja la copia en GMAIL (aunque se puede configurar para que lo elimine)
SMTP: deja una copia de los enviados en el OUTLOOK y en GMAIL
Si utilizas una cuenta CORPORATIVA.
Cuando recibes correos los descarga en OUTLOOK y deja la copia en el servidor de la nube (aunque puedes configurar que estén siempre allí, o que pasados X días de haberlos recibidos, los borre de la nube), dependiendo del espacio contratado
SMTP: los correos solo quedan en local dentro de OUTLOOK , y no en la nube.
Si borras un correo del OUTLOOK, aún dispones una copia en la nube para poder consultar o poder descargar
IMAP:
Si utilizas GMAIL o una cuenta CORPORATIVA:
Todos los correos se consultan directamente en la nube, tanto los enviados como los recibidos (aunque los descargados están como en caché tanto en SMARTPHONE como en OUTLOOK). Siempre que entras a consultar los correos, el sistema sincroniza automáticamente en la nube y comprueba si se han borrado, movido, o creado correos o carpetas.
Si borras un correo de la bandeja que sea o de la papelera , ya no se pueden recuperar (porqué los has borrado ya directamente del servidor)
Si utilizas una cuenta GMAIL WORKSPACE corporativa (con un administrador), si borras algún correo, tú no los puedes recuperar, pero el administrador puede decidir desde cuantos días puede volver a recuperar los correos que borraste
Más o menos lo explico así, en plan rápido