Yes it may be a threading problem. Contact RIM TSupport with your BES logs for the days when the slowness was experienced. They should be able to find something. Just for your information, in general you would want ONE thread to service some 8-12 handhelds.
BTW, BlackBerry email all along is not meant for "REAL TIME" and instant delivery, make sure this expectation and record is set straight to your end-users.