Reducing your messagebase is easy, just delete messages. However, you mentioned that you can't miss lots of your messages, so the best way is to store old messages in separate folders.
It may seem odd, but it's not the total size of your message base that determines the time needed, but it's the size of the folders that are being compressed.
Let's first explain what compressing is. When you delete/move a message from a folder, the message won't really disappear from your folder, it's only marked as deleted. (That's why you can browse through the deleted messages) When you compress a folder, TB checks whether there are deleted messages and when there are any TB will compress it it, while it'll do nothing when there aren't any deleted messages.
Resuming: a 20 MB folder without deleted messages wont take any time. A 50 kB folder with 100 deleted messages won't take much time, since it won't need much time to build it up. But a 10 MB folder with one delete message will take the most time.
When you look into TB's directory structure on disk, you'll see that subfolders are separate directories with their own message base. So when you'd like to keep your regular storing system, you simply create  a couple of subfolders called archive (or whatever) and move your oldest messages into them. The first time you set out to compress your messagebase after this, it'll take some time, but you'll find it'll be better the next time.
Note that it isn't just the number of messages and their that makes a messagebase big, but also the number of attachments and their size. I've got this one folder with the setting to keep messages for 365 days and it was really slow in maintenance while exiting, even though it just had less than 100 messages, but every month I'm getting a Word document attached in that folder and some of those attachments were really huge like filesizes of 35 MB, due to the inefficiency of MIME encoding that makes those messages something like 50 MB. So that made a huge folder of 250 MB, considering that my folder with the most messages (23000) is only 82 MB. What I did was keeping those attachments as separate files and delete them from the messages, that was quite an improvement in speed when compressing.
That leaves us to the Inbox. All of your received messages come in the Inbox, from where they'll be filtered to other folders or manually transported. In order to speed up compressing of your Inbox, you'd better not keep a real amount of messages in it (or lots of attachments), especially since the Inbox a high traffic folder is easily corrupted. (I've never had any troubles with it, but I've heard lots of people complainingabout it, especially those who keep almost everything in it.)
These are the guidelines for proper folder use as I see them. I hope it helps.
BTW Even though TB supports (depending on your OS) folder message base larger than 2 GB, a folder that big is never a good idea.