Slow Outlook - Exchange 2007

Hello,

I have a Exchange 2007 SP3 RU3 on a CCR configuration ( 6 Servers total, 2 for each role, MB,HT,CAS)

I have 5 DB on my exchange, which are divided by country.

Some of the users on some of the DBs are having problems with outlook, when they try to sort their inbox, or navigate thru folders, outlooks hangs for like a second or 2, this only happen on Terminal Servers since cache on outlook is not avail, for laptop users they are all ok.

I am been trying to figure out what is causing it, but not luck, I have a ReplayLog too big on one of the DBs from where the users are complaining about, but I want to run a full backup before messing with anything.

Things that I want to do is:

() Fix the  ReplayLog
() Re-Index the catalogs, and this is becuase on MB1 ( Remmember I have 2 MB servers ,MB1 and MB2) the catalog folder of the DB is 8 GB while on MB2 is 17GB ( Primary is MB1), so I want to re-index and see if the fix the issue.

Any ideas if I am on the right track, or the "problems" that I am having with exchange will not affect the performance of the outlook for the users?

Thanks!