Any unencrypted language is decompilable. Think about it: the computer/virtual machine/interpreter has to be able to run the program, right? To do that, it must be in some sort of order. The logic must be there some how. A decompiler is just a program that goes through the code (whether it be plaintext, bytecode, or machine code) just like whatever is running the code, but instead of running each command, it spits out equivalant source code for that command. (That's just a simplication, of course; decompilers need to be a bit more sophisticated to handle a command that maps to several lines of lower level code, for instance).
So, knowing this, you should be able to see why decompilers are *not* a good way to secure source code. The only way source code would really be secure is if a computer/virtual-machine/interpreter/whatever-is-running-your-code had a way to natively encrypt/decrypt the source. (Think: you supply a password when compiling your program, and your user has to enter this password when running your program). I do not know of any language that has this feature, not even Java, probably because it would be a huge pain in the ass to users.
That means the decryption algorithm is standardized and known. (If it is not, the VM is subject to the same decompilation issues as the bytecode was in your other scenarios.) That defeats the entire purpose and makes decrypting the "natively" encrypted bytecode trivial.
There is no scheme ever that works — by definition. The only way to prevent reverse engineering is having control of the hardware.
I got the idea from diotalevi. I don't remember his exact words, but he said Visual Basic might be what I'm looking for. On the other hand, he also told me never, ever to use Archive::Tar, and disappeared when I questioned him, leaving me and another monk confuddled in CB. He might have been being sarcastic both times. Reckless sarcasm --.
You said "(That's just a simplication, of course; decompilers need to be a bit more sophisticated to handle a command that maps to several lines of lower level code, for instance)"
Therein lies the major difference between a machine language interpreter and a machine language to high level language compiler. The former obviously must exist to run the program, but the latter is not necessary in programming, and is difficult to build.
This is basic stuff. I'm not going against common computer industry knowledge with this. Compiled programs for which there is no complete, free, well known decompiler are more safe from piracy.
I was in need of a Visual Basic 6 decompiler and searched for one without referring to the webpage full of decompilers that you linked to. I found a couple of links to decompilers for older versions of VB, I found someone saying that VB decompilers for new versions don't exist, I found several people asking for one and receiving no answer, and found several VB "decompiler defeaters," one of which the web page you linked to lists.
Looks like Visual Basic might be safer than Perl after all.