Actually, the -i thing DOESN'T stop anyone from removing a file. If the user types in rm FILENAME, the file is removed regardless of whether or not a -i is in the directory. This is an old Unix hackers trick to slow down someone using rm *. Because -i will almost always be the first directory listed after . (dot) and .. (dot dot), the rm command interprets this as an argument, rather than the file that it really is.
The answer to your question is you really can't protect users from themselves. Hopefully, you don't let them have any privledged accounts (like root) where they can do any real damage. If a user is smart enough to use the find command, they'll also find a way to delete a file using it.
Chris