I found that sometimes if you have too many (deleted) messages in the inbox it wll slow the system down substantially. I contacted support and they logged in and cleaned out all the deletes over a year. It made a significant difference.
You can go to user preferences and under messages click automatically clear deleted messages older than X years and I have that checked now but not sure if that will clear it as effectively as they did remotely
