Mark,
If your users don't listen, then you as an administrator need to do this for them by cleaning out their own folders using some means of archival or by the use of Mailbox Manager to move items out of their critical path folders.
If they don't keep item counts under 5,000 items or so, then they will at some point come to you stating that when I click on this folder, it took x amount of time to render that view and this is unacceptable
If they are using the Show in groups option or doing any custom views outside of the defaults, then render time will take that much longer.
Just think of this, when you click on a folder, we have to query every item in that folder before rendering the view back to the client and the more items you have, the more time it is going to take to generate that view. Unfortuantely, we don't have any paged typed functionality to build the view in chunks currently, but we are doing some significant work in the next version of the products to minimize these problems.
Identifying an Exchange server as slow can have 100 different root causes, so can you be more specific as to what slow means?
If all else fails and you are still stuck, I would open a support incident to determine if the server slowness is a server side issue or it is a perceived issue on the client side.