But this would raise a binding error:
baz: [foo] make object! compose/only [ foo: 2 bar: (baz) ] => ** Baz already bound to context
A problem with outlawing binding is that in the general case, code doesn't really know how much binding it has been through already. That can be the loading process behind a module... or an abstract dialect that has slots in it where you can put code.
Just consider things like the OPERATION abstraction just added to Whitespace. You want the code in the body to be able to see library definitions you load in to the module as a whole--that foundation is done by a bunch of binding. Then it's building a function behind the scenes...a process that means binding to locals and (synthesized) arguments.
While it's using "global" variables to access parts of the virtual machine state, this needs to change to something that's more narrow. Maybe it gets at everything through one variable like your STATE approach, so it would have to say things like state/stack. But as I mentioned that feels heavy-handed... I think it's nice to just have an implicit stack variable since messing with it is so common. So broadening this set out to N implicit variables seems better, maybe just a few shorthands (e.g. STACK allowed instead of VM/STACK, but other things might require VM/XXX)
In such a layered world, what kind of rule could MAKE OBJECT! enforce to disallow binding? What's the test it does on a block to say "hmm, this is too bound up".
Yep! 
But I'm very glad you are picking up involvement in this line of thinking. Because having an interest in this topic at all seems to be pathologically absent from most of the Rebolverse (whereas I believe it is kind of the essential question of what the semantic basis for the language could possibly be...)
In terms of inch-by-inch progress: the baby step I've been trying for starters is to stop mutable binds from happening to CONST data. Since functions make their bodies CONST, that means anything that would "bind implicitly" (such as MAKE OBJECT!) would have to be switched from BIND-style binding to IN-style binding.
There's actually still some violators, due to a lot of little technicalities in a very sprawling and organically evolved codebase. But good news is that the compiler can catch the violations (just by making a C++ build). There just have to be little "ignore the violation" tweaks in--for now--for some bits to run.
I hope you take a look through the steps to upgrade the Whitespace example and some of the questions it raises. Right out of the gate, it needed a variant of MAKE OBJECT! which didn't broadcast the bindings down through the body...and you can see how I did that in the CATEGORY implementation.
This is a very excruciatingly manual form of what I talk about in "breaking MAKE OBJECT! into multiple operations". But this is a very common need and people shouldn't have to write their own version of it.
I doubt the needs are all that different from your Parse Machine. But the advantage the whitespace case has is that it's a rather easy-to-understand and documented scenario that can be compared with implementations in other languages. So I hope you can chime in on helping to solve these fundamental and mission-critical problems...what are the steps, what do we call them, and how does it all plug together to make a compelling story.
If a Redbol can't solve problems like this, then the big-picture promises are basically snake oil. People are merely going down a Turing tarpit of making weirdly brittle spaghetti code in Rebol--simply because it can't stop you from solving a problem using it (not because it's providing material support). I think Ren-C stands on reasonable ground to build the Actual Value solution. But it needs your help.