To fix this I found a Microsoft Technet Article "Background Cleanup interval for a mailbox store is missing". It supplies an easy fix for my problem.
Open a registry editor, such as Regedit.exe or Regedt32.exe.
Navigate to: HKLM\System\CurrentControlSet\Services\MSExchangeIS\
Create a DWORD value called Background Cleanup with value data of 60000 (decimal) or 0xEA60 (hexadecimal). Do this for each mailbox on the server.
Close the registry editor. To make the changes take effect, do one of the following:
Dismount and mount the affected information stores.
Restart the Microsoft Exchange Information Store service.