See section 9.1.5 http://www.gnu.org/software/findutils/manual/html_node/find_...
It walks through many of the same issues as the OP, but with more sophistication.
It also explains "+", which is used in place of the traditional ";" to essentially get xargs type argument accumulation, but within find.
That is,
find . -name '*~' -exec rm {} \+
-print-0 | xargs -0 does not fix the race condition.
The problem is someone can swap in a symlink after the find, and before the xargs.
It does not delete the file using the entire path (which may contain a sudden symlink).
It's not possible to do this safely using xargs.
Take a look also at -execdir which does the same thing - changes to the directory first, and runs things from there. -exec is not safe and should not be used.
xargs is not safe if you are running against a directory not your own. You should use find and -execdir instead.
Yes, the original authors of posix made a mistake here.
> Also, rant rant, I really don't understand why find was extended with -delete in the first place.
I'm hoping you understand it now.