Pues que me lo expliquen melado, la primera vez no le di importancia, pensé que sería algo puntual pero ya es la segunda vez.
Además, ahora me acuerdo que al borrar el privado y al volver a la bandeja de entrada, ponía "48 de 50", es decir, realmente se borró, si la tenía llena y borré solo uno, debería haber puesto "49 de 50".
EDITO: He intentado reproducir el bug desde la versión normal y no me ha pasado, he recibido dos MPs en dos momentos distintos con la bandeja llena borrando un mensaje random antes y sin problemas.
Saludos!