The problem is that once you've downloaded the file, it automatically gets assigned the same trust level as all of your other files.
Why not take advantage of the multiuser nature of the underlying system? Make any program that can download things (email clients, web browsers, instant messenger programs, IRC clients...) run as a separate user, and save files under that username.
It could be something as simple as your user name with :untrusted appended to it.
It wouldn't be too hard to train Gnome and KDE to know that files from user "username" are normal, but files owned by "username:untrused" have come from the great wilds beyond the fence and require the user to bless them explicitly before they can be executed. The underlying system doesn't need training at all if the umask is set properly.
It uses the existing infrastructure, and it requires relatively few changes to work. Most of the effort is in the setup; adding a user would require setting up two accounts, one of which (the untrusted account) would be a locked no-login account with no home directory.
From the command line, the user could "bless" files with chown(1), and I suspect the "stupid people get what they deserve" rule applies to someone who opens a terminal and directly invokes a downloaded script without vetting it. For actual executables, you'd be foiled by the lack of group/other execute permission in the umask if you tried to run it.
On the GUI side, all that really needs to be done is the launchers need to check to see if the uid of the file is suspicious (which they ought to be doing anyways...), and if so, bring up an appropriate dialog, that could be one of:
- the file is owned by some other (non-root) user on the system and is effectively executable, do you want to [make & run owned copy] [run] [cancel]
- the file is owned by your untrusted alter-ego, and is not executable, do you want to [take ownership & open] [open], [cancel]
- the file is owned by your untrusted alter-ego, is executable or contains a script, dialog has a big picture of your parents looking stern, [pick up the soap][flee]
It might even be worth saying you simply can't bless executable files owned by your untrusted alter-ego without dropping to the command line and using chown.
The other part of this is that making magic executables with .desktop was a mistake. It wouldn't have been hard to use "shabang" to make .desktop files legitimately executable through the standard system, at which point they'd even (!) work properly from the command line, and they'd inherit the security mechanisms built around file access. Every alternate path to execution in the system is another possible point of failure for security.