Decompiling and recompiling before execution would not be acceptable by end users, as it would be just too slow. In any event, being able to decompile and recompile in no way provides any assurances against malware. Besides, I would think such round trips would always be possible, even when binaries are obfuscated. The resultant decompiled source may be totally impossible to understand by a human... in fact it may be nothing but a bit of bootstrapping code and a gigantic byte array, but the decompile/recompile round trip would still work.
Full blown VMs aren't necessary. Sandboxes and jails are generally good enough. Either approach only works, however, for standalone applications that need no/minimal access to other applications or OS resources. Doesn't mean it's a bad idea, it's just not a universal solution.