Hola,
Yo creo que hay algo de retraso entre que borras el mail y se actualiza en el servidor de google. Por ejemplo, yo cuando me levanto borro mails desde el móvil, y cuando llego al trabajo (más o menos 45 minutos después) ya no están, pero si lo borro desde el móvil y al momento voy a mirar por el pc sigue estando.
Como bien dices, si le das a actualizar manualmente se actualiza al momento, pero es un poco coñazo.
Saludos.