Para remover um arquivo, você precisa ter acesso de gravação ao diretório em que está, para modificar o arquivo, é necessário ter acesso de gravação ao arquivo. São duas operações diferentes.
Portanto, se você quiser impedir que um usuário remova um arquivo, ele não poderá estar em um diretório que o usuário possua, pois, em última análise, ele sempre poderá tornar esse diretório gravável para si mesmo.
Você pode fazer isso com ferramentas mais granulares, como ACLs para o SELinux, etc.