CRM 4.0 tidies up deleted records via the asynchronous service every 24 hours. To force an immediate cleanup follow the steps:
1. Mark the database to run the deletion tidy up immediately by running the following SQL commands. Take care to update the correct deletion service if your CRM server hosts multiple organizations.
// getdate() gets the current date and time
SET NextRunTime = getdate()
// Operation Type 14 is the deletion service
WHERE OperationType = 14
2. Restart the Microsoft CRM Asynchronous Service