Thomas, the cleanup process does not run immediately, but usually within 24 hours.
Also, the auto cleanup for Deleted Items does not work as most people would expect. It purges based on message date, not 30 days after it's deleted. So lowering the threshold to 3 days isn't necessary -- just delete a message from 2 months ago.
Go here and vote up this thread to get it fixed:
Kevin