That doesn't necessarily mean the author of the utility programs has to be able to send updates without your approval, or that they need to be able to receive communications from their utility program, or that you can't delegate your approval of application updates to a third party who vets the code, or that the utilities can't be small and clear enough that you don't have any doubt about what they're doing, or that all programs need to have full access to your files, or that you can't store your files somewhere where you can roll back undesired deletions.
The only reason you'd want to run such a utility would be to clean out the .tmp files within a particular sandbox. In that case, you'd give permission for it to operate on the whole of that particular sandbox's contents. Worst case, it trashes that sandbox, then you roll back to your previous backup.
They were supposed to have a sandboxing scheme along these lines in the OLPC.
If your files belong to your applications instead of to you, or if your sandboxes don't nest, then your sandboxing scheme is pretty lame.
Most of the time there are worse cases than just deleting your documents: the utility could send all of your documents to its owner over the internet. You can prevent this with sandboxing policies too; KeyKOS solved an analogous problem in the context of a multiuser non-networked mainframe. More difficult is to keep it from inserting backdoors into your programs or subtly corrupting your files.
I don't see how the solution "then you roll back to your previous backup" is dependent upon only the utility only having access to a single sandbox. It seems like it works just as well if you give it access to everything except your basic UI (and the TCB it depends on, e.g. the kernel, the bootloader) and your backups.
I just didn't want to explain capabilities for the nth time, so I thought I'd throw the OLPC at him. Even a sandboxing scheme like the OLPC's addresses his objections. Not sure if it was supposed to nest.
I was arguing that the other guy was right that sandboxing in itself is not sufficient; you still do need to have a way to deal with code that you give the full run of your system, even if you keep the amount of that code to a minimum.
People have been researching other security models for decades now. I'm afraid I have to say: they're way ahead of you!