Are you saying that you have to delete them in batches? E.g. instead of deleting 30 messages at once, you select all the ones you can see on the screen, delete them, then select the next batch, etc..?
Verizon 8130 (on the bench, now
Verizon 9530 (replaced by VZW 4 times, then with a 9550)