I'd say dualism absolutely solves this problem, or at least can provide the tools to do so.
(I say all of this as a devil's advocate, and nothing more)
Imagine that heaven exists, and is a kind of meta-universe that our reality is a subset of. It has access to a higher order of systems than those within its subset, and they can say things about truth that the reality subset cannot (because of incompleteness; a system sufficiently powerful to say all true things is unable to prove all of them). Things that we cannot write proofs about, that we must accept as axioms (for example, in the space of ethics and morality) may be trivially expressible in the higher-order logic of meta-heaven.
Say now too that the dualistic, non-material constituent, the Soul, exists in this meta-heaven. It has access to this higher-order reasoning, and can make causal decisions according to it. However, to its physical coupling in the reality subset, these decisions will appear to be random and non-causal. They will be the outcome of nothing from within the universe. Manifestation of Free Will and Randomness can be considered to be indistinguishable in this sense, from the perspective of something inside the system that they are operating on.
It still pushes the problem 'up' one level, but who knows what the physics of a meta-heaven looks like. We can't even imagine it, in the way that a computer can't imagine its own halting. Hence all the talk of ineffability in the older dogmas of the world.
Similar to your idea is Kant's "thing-in-itself", which is just a way of saying that for any given object, there are attributes to it we're not able to observe - indeed, attributes we can't even imagine.
We're trapped in our brain, behind a wall of sensory apparatus. There's no reason to assume that our senses provide the complete totality of reality. And if there are aspects of reality we cannot sense, then there is more to reality than we can ever know. Kant called these attributes the "noumenal" world, while what we can see and observe is the "phenomenal" world. However, these are NOT separate areas - just two aspects of the same thing. Not dualism.
Schopenhauer took this to the next step and said that there are aspects to ourselves we can't observe, so part of our selves exists in the noumenal world. The phenomenal world is deterministic, but if we have free will, it must exist as part of the noumenal world.
Isn't that ignoring the fact that we can build tools to translate unsensable things into sensable ones? E.g. infrared cameras allow us to sense infrared which we normally aren't able to. Theoretically we should be able to build tools to sense anything which has an effect on the world. If it has no effect on the world then does it even exist?
There's still things that are impossible to accurately measure from within our reality.
We, for instance, can't know or measure the precise state of things as they would've been had something different occured than what actually occured at an earlier time.
This is especially obvious in the realm of quantum mechanics, where you can't know what you would have measured if you had measured earlier or later than you did (I hope my interpretation as a layperson was correct here). That information just doesn't exist in our reality, but it may exist in some higher order place where all those realities can be observed.
Viewing infrared extends one of our existing senses. Kant's point was that could be attributes of the thing that do not, in anyway, relate to our senses.
These attributes can't have any effect on the phenomenal world, or they'd be detectable, and by definition, they're not detectable by us. Unless, of course, our free will is part of the noumenal world, and our actions in the phenomenal world are simply one way of viewing our will.
I think that's just hiding the internals of the non-physical part of us from view, but it doesn't change anything. I already addressed the status of non-material components of a person in my post - if they are part of the person then they are part of their state. Whether you can 'see into' that state or not doesn't make any difference to the fact that it's still part of you and still a precondition of and an input into your decisions. They may be the outcome of nothing in 'this universe' (ridiculous concept, what does universe even mean if the definition isn't, well, universal?), but they are still the outcome of something in 'a' universe and that something has state.
Even randomness or the appearance of it doesn't make any difference. A person's state might very well include a source of randomness, in fact it almost certainly does. See my comments on this elsewhere in the thread.
Separating the two bits like this lets you have your cake and eat it too; it allows for a causal explanation between a person's (comprising both their physical and non-physical) state, and their actions, but that total state (and therefore, responsibility) can't be completely reasoned about in the reality that we exist in. They appear indistinguishable from the 'uncertain decisions' you mention in your first post, but are (in the whole picture) simultaneously causal/responsibility-inducing, and completely inaccessible to some Laplace's Demon.
It's why this kind of system usually is accompanied by a whole meta-set of of punishments and rewards as well. Since there's no way to perfectly reason and judge in our system, we have to hope that someone who has access to the higher system will provide the correct judgement, being able to see the total picture of responsibility.
It's also completely untestable, for the very reasons it 'works' as an explanation at all!
Untestable theories don’t explain anything by definition. If it influences the physical world in an ongoing way, in principle it must be testable. If it’s not testable, that can only be because it is not making a difference.
What if an "out-of-this-world" thing is a part of the state? You can't observe its internal state, so you can't emulate its functioning, even if it's completely deterministic "in a different dimension". This can be literally compared to having a complex state variable and only being capable of observing its real part, or functions of it that are entirely real. (See quantum mechanics for examples of this.)
Do you mean something like: There exists a multiverse in which the soul gets to choose which element of the multiverse it resides in moment to moment. So while each element of the multiverse (a particular reality) is completely deterministic, the one experienced by the soul is chosen.
Sure, if you want to keep the 'influence' between the two systems to a minimum.
If you allow the mutation of the subset reality by a soul in the meta-heaven, then you can have it all operate in a single universe; the soul is capable of adjusting the nondeterminism of particles in the brain, thereby making decisions happen that appear random to us, but are informed by a higher system of reasoning. In the way that a programmer might adjust constants, or a video game player might choose stats.
And just want to reiterate: I'm not trying to advance this explanation! Just fun to think about.
(I say all of this as a devil's advocate, and nothing more)
Imagine that heaven exists, and is a kind of meta-universe that our reality is a subset of. It has access to a higher order of systems than those within its subset, and they can say things about truth that the reality subset cannot (because of incompleteness; a system sufficiently powerful to say all true things is unable to prove all of them). Things that we cannot write proofs about, that we must accept as axioms (for example, in the space of ethics and morality) may be trivially expressible in the higher-order logic of meta-heaven.
Say now too that the dualistic, non-material constituent, the Soul, exists in this meta-heaven. It has access to this higher-order reasoning, and can make causal decisions according to it. However, to its physical coupling in the reality subset, these decisions will appear to be random and non-causal. They will be the outcome of nothing from within the universe. Manifestation of Free Will and Randomness can be considered to be indistinguishable in this sense, from the perspective of something inside the system that they are operating on.
It still pushes the problem 'up' one level, but who knows what the physics of a meta-heaven looks like. We can't even imagine it, in the way that a computer can't imagine its own halting. Hence all the talk of ineffability in the older dogmas of the world.