Also, Microsoft Exchange engineers went over the server awhile back with some monitoring tools and it seemed fine (Exchange 2003 on a 2003 server).
Microsoft's analysis was good and valid when they performed it; I'm sure of that ... but I bet mailboxes have grown, you've added some BES users and your environment isn't quite the same.
Take an assessment for what it is worth. A look at the current environment; I always find the best part of any assessment to be the recommendations on what to do going forward. ... well at least thats what I hear back from my customers.
Its entirely possible that something happened within BES during the upgrade, but unfortunately its not a cut and dry thing due to all the components involved.