As mentioned perviously, we identified a problem with the maintenance plan clean-up task that was introduced in SQL Server 2005 Service Pack 2.  Well, the good news is that we have now released a hotfix to correct the problem which can be downloaded from here

The corresponding knowlege base article is available here Microsoft SQL Server 2005 Service Pack 2 issue: Cleanup tasks run at different intervals than intended.