A exclusão de um diretório depende dos direitos de seu diretório pai e não de seus próprios direitos. Se o usuário tiver permissão de gravação para o pai, o diretório será deletado, caso contrário, não.
Portanto, se o usuário não precisar ter permissão para criar ou excluir diretórios / arquivos no mesmo nível em que o diretório a ser protegido, isso deve funcionar:
chmod 755 /the/parent/dir
Se alguns usuários ainda tiverem permissão para modificar o conteúdo do pai, o pai deve pertencer a um grupo cujos membros sejam esses usuários e esse grupo deve ter a permissão de gravação:
addgroup bigguys
chgrp bigguys /the/parent/dir
chmod 775 /the/parent/dir