so you're using a multiple version Exchange environment in Native Mode (for 2003)? the reason i ask this is because the cdo.dll version will vary from 2000 (6.0) to 2003 (6.5). can you confirm that your main mail servers are running Exchange 2000 SP3 with the August Post-SP3 Rollup patch (6.0.6603.0 is the corresponding cdo.dll for that patch that you are using)?
are you showing any pending messages in the queues? is it only for just a handful of the same users, or is it present, at some time or another, for the majority and/or all of the users? if the users are specific to certain Exchange servers, are they only on the Exchange 2003 servers or also the Exchange 2000 servers? what's the server load showing for CPU and memory utilization (what are its specs, as well)? what kind of database are you running for backend (MSDE7, MSDE 2000, SQL 2000) - same server or separate server?
since you are now running the latest service pack, have you tried to call RIM back and let them know that you are still having issues?
i think that'll do for now.