if our users get over a certain number of messages in the trash, they won't delete when multiple messages are selected.

You can Select All, then delete. Messages just repopulate the list.

Fix: view a message in the trash and delete it from there. Then select all and delete. view another message and delete, then select all and delete.

So you have to delete 1 message at a time in between mass deletes.

Kinda wierd.