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 http://www.microsoft.com/downloads/details.aspx?FamilyId=e2c358a1-ecc4-4c49-8f65-daa6b7800eec&displaylang=en

The corresponding knowlege base article is available here http://support.microsoft.com/kb/933508 Microsoft SQL Server 2005 Service Pack 2 issue: Cleanup tasks run at different intervals than intended.