Es muy probable de que tenga configuradas las cuentas de correo en formato de POP3. Así también es muy probable de que tengas configurado mantener una copia de los correos en el servidor. Tendrías que ir a las opciones y setear eso nuevamente al agrado tuyo. Para casos muy similares como el tuyo es de sugerir de que el borrado de los mail se haga vía webmail por la cantidad y criticidad de los correos. Se sugiere de que configures tu cuenta de correo con IMAP que gestiona los correos desde el servidor. Si lo que querés es borrar una cantidad de correos electrónicos de más o menos esa envergadura que es lo que decís sería sugerible de que utilices en formato de IMAP en donde en formato de IMAP gestiona los correos directamente desde el servidor no desde el cliente como lo hace POP3 o cómo se sugiere que lo estás haciendo. Advertencia: IMAP gestiona los correos desde el servidor algunas acciones como borrar NO tienen vuelta atrás. Una vez que los borres NO los recuperarás. Al igual que vía webmail.