No se que tipo de cuenta tienes pero prueba esto y depende de como se haya vaciado. Si es POP igual lo has borrado pero sigue estando en la papelera con lo cual solo debes recuperarlos de allí. También puede que los hayas movido a otra carpeta. Si es IMAP también sirve lo que te he dicho antes pero ademas debes tener en cuenta que igual has entrado en tu correo desde otros dispositivos y lo has borrado de ese dispositivo provocando que se borren en todos. Otra opción es si tienes copia de seguridad restablecerla.