Si te vale con que cada usuario pueda borrar solamente sus propios archivos pero no los que han creado otros usuarios, lo que yo haría es crear un grupo común para dichos usuarios y habilitar el GID y sticky bit en el directorio. Creo que es la opción más sencilla y que menos problemas te va a dar.
Si realmente necesitas que nadie pueda borrar nada, puedes lanzar chattr +a sobre el directorio y además aplicar un ACL por defecto en ese mismo directorio para que todos los archivos que se creen dentro sean solo de lectura. El problema de esto es que tendrías limitaciones a la hora de dejar a los usuarios crear subdirectorios libremente.