Why do I get "Operation Not Permitted" when I try (as root) to delete a file that does not have the `restricted` flag set
Turns out that in addition to the restricted flag, SIP protection can be invoked on a file by giving it the com.apple.rootless attribute. Attributes are not shown by ls -lOd, you need ls -l@d to see them. (Strictly speaking, the d option is not necessary, it is there so that when you do ls on a directory, you only get information about the directory itself without also getting info on everything in the directory.)

Much more information on this is available here.