Can someone delete my non-empty directory from a write-all directory without having write permissions on it?
Não.
Is keeping the directory non-empty and non-writable for others a safe way of preventing other users to delete the folder?
Sim.
rmdir
não funciona em diretórios não vazios e, sem acesso de gravação, eles não têm como esvaziá-lo.