have you checked to ensure that the owner of the maintenance job (the identity that it runs under) has delete permission on the server folder where the backups are stored?