hi Warren,
Part of the 8x8 high availability infrastructure is that all customer phone systems run both an Active and Backup. In the event that something becomes a problem on the ACTIVE system, an immediate failover to the BACKUP takes place. In some cases the data on the BACKUP may not be completely in sync.
So, if there was a switch to the backup shortly after those messages were deleted, the BACKUP version of the phone system may not have been updated yet.
I'm offering this as ONE possible explanation for what you're experiencing.
Steve