Lo que ocurre con la Galería (y también con el Reproductor de música) es que no se actualiza hasta que no recargas el contenido multimedia del móvil. Puedes hacerlo reiniciando por ejemplo, yo tengo un widget en la pantalla principal que lo hace.
Cuando copio MP3 o fotos al móvil desde el PC le doy a ese icono y entonces se actualiza en todos los programas del móvil que usen fotos o música (y hagan uso de la lista que proporciona ese servicio, hay otros programas que solo se basan en acceso por directorios que ignoran esto)
Así que en respuesta a tu problema, después de borrar la foto tienes que actualizar el contenido multimedia del móvil.
