As standard CRM 4 deletes records, marked with deletionstatecode=2, on a 24 hourly basis.
Mitch Milam has written, an unsupported, utility that forces the deletion. The utility can be downloaded from his blog: http://blogs.infinite-x.net/2009/08/26/free-utility-run-crm-deletion-service. After installing the utility the exe can be found in \Program Files\CRM Accelerators\Run CRM Deletion Service.
There is also a utility, by Microsoft, that allows you to change the frequency of deletion and re-indexing. This utility is called Scale Group Job Editor. This tool can be downloaded from: http://code.msdn.microsoft.com/ScaleGroupJobEditor
