Um, 21,000 messages is really pushing the performance envelope of a mobile device...
Sounds like the app's database got really slow, hence the slowdown. You can try Menu -> Compact the database in the main window (account list), but I doubt it's going to have a lasting effect.