This is really a design flaw with AC. It should not slow down so much from deleted items.
Loading 30k messages from the main computer's database is an awesome task for any CPU.
As some famous programmer said "It's not a bug, it's an undocumented feature." As your doc commented, access to deleted messages is a frequent necessity. I'd rather it be me that chose when to empty the trash. The problem is that nobody told you. Until now.