Full disclosure: I am blatantly stealing this idea from Joel Lindstrom at Customer Effective, as outlined in this article:
Preparing for CRM 2011: How to Make your Microsoft Dynamics CRM 2011 Upgrade Faster
Run the deletion service. In CRM 4.0, if you deleted records, the records were not immediately deleted-they were flagged for deletion, then the CRM deletion service came along, usually within 24 hours, and deleted the records.
One problem that can happen, especially if large numbers of records were bulk deleted, is that records can get stuck in the “soft delete” state.
In 2011, there is no more soft deletion of records-they are deleted immediately from the database when the records are deleted in CRM. When you upgrade, the upgrade process will hard delete any leftover “soft deleted” records. If you have many deleted records in your system, this step can take a while.
Before you upgrade, you may want to search your main entity tables to identify if you have a large number of soft deleted records still sitting in your database. For example, the following query will identify any deleted records that still exist in the account tables:
select * from accountbase where deletionstatecode = 2
If you find that there are high volumes of deleted records still residing in the database, you can clean them up with a free tool such as Mitch Milam’s "Run CRM Deletion Service" utility.
Sorry Joel, but it was something I forgot to put on my own list and just too good not to repost.