Sean from the support group just let me know that there is a new tool to help customers out. In 3.0, I used to just stop the Deletion Service. With this tool, you can change the DeletionService and Re-Indexing service jobs in CRM 4.0. You can set the next run date/time of a job as well as change the schedule at which the job will continue to run automatically.
There is some issue tracking and more details here at the link!