Are your backups stored in subfolders? Is the delete option set to traverse the subfolders?
Are your backups corrupt? The deletion process won’t delete files if the files are corrupt.
Is the backup being done by the native maintenance plan, or are you using a third party tool such as LiteSpeed for SQL Server?