After digging into this topic (yay, can now post links !), I wonder if the issue might be related to the recent “Granular” scope changes, that seem to be very partially documented, especially regarding recording deletion.
As our config pre-dates those changes, it is using the now-classic scopes (and does have all three recording:*scopes enabled)