A new hotfix has been released for SQL Server 2005 Service Pack 2. This hotfix fixes an "...issue that caused maintenance plan cleanup tasks to remove data before the specified cleanup interval".
If you have already installed SP2, you'll need the hotfix. If not SP2 has been updated to include the fix. The new version number for SP2 with the hotfix is 9.00.3050.