<p>I've got a maintenance plan that executes weekly in the off hours. It's always reporting success, but the old backups don't get deleted. I don't want the drive filling up.</p>

<p>DB Server info: SQL Server Standard Edition 9.00.3042.00 </p>

<p>There is a "Maintenance Cleanup Task" set to </p>

<p>"Search folder and delete files based on an extension" </p>

<p>and "Delete files based on the age of the file at task run time" is checked and set to 4 weeks. </p>

<p>The only thing I can see is that my backups are each given their own subfolder and that this is not recursive. Am I missing something?</p>

<p>Also: I have seen the issues pre-SP2, but I am running service pack 2. </p>

My understanding is that you can only include the first level of subfolders.  I am assuming that you have that check-box checked already.
Are your backups deeper than the just one level?
Another thought is, do you have one single maintenance plan that you run to delete backups of multiple databases?  The reason I ask this is because the way I could see that you would have to do that would be to point it to a folder that was one level higher meaning that your "include first-level subfolders" would not be deep enough.
The way I have mine set up is that the Maintenance Cleanup Task is part of my backup process.  So once the backup completes for a specific database the Maintenance Cleanup Task runs on that same database backup files.  This allows me to be more specific on the directory so I don't run into the directory structure being too deep.  Since I have the criteria set the way I want, items don't get deleted till I am ready for them to be deleted either way.
Tim