Is it possible that we live in a universe where some things are truly deterministic and other truly random and the difference between those two things is how their particles are arranged?
Perhaps. Consider unstable Lagrange points, which have the property that objects traveling through them have an undetermined aspect to their ultimate trajectory. This is because at such points, the forces of gravity cancel, and infinitesimal differences can make all the difference. This means that infinitesimal forces can have a non-infinitesimal effect. Now, must our universe allow true unstable Lagrange points? My don't-have-a-physics-degree hunch is "no", either by simply disallowing certain starting configurations, or quantizing space somehow.
We could then consider whether allowing the forces of gravity to cancel merely allow randomness to rear its head, or actually allows another causal order to manifest itself. Something to be wary of is an implicit identification of 'determinism' with general causation, over against singular causation (comparison). In my experience, compatibilism is defined against general causation, not against any and all forms of determinism. For example, from the Stanford Encyclopedia of Philosophy:
Within this essay, we shall define determinism as the metaphysical thesis that the facts of the past, in conjunction with the laws of nature, entail every truth about the future. (Compatibilism § Determinism)
I've taken to describing this as monocausation: there is one causal power in play, constituted by the laws of nature (not to be confused with scientific laws, which are understood to be approximations). And so, compatibilism is an attempt to achieve something that looks like free will without adopting a different metaphysics of causation. In other words: there is an implicit commitment to the denial of agent causation, where agents are irreducible sources of causation in addition to the laws of nature. Of course there are costs to abandoning monocausation: how exactly would two causal powers interact if there are no "global rules"? Every philosophy has to bite its bullets.
You can find a fairly well-developed alternative to general causation/determinism/monocausation in Gregory Dawes' Theism and Explanation. There, he asks whether "God did it" could possibly suffice as an informative explanation. Let's not get too caught up in theology; what he's really asking is whether agent causation could possibly provide explanatory power over and above what you get with general causation. His answer is yes: a good explanation has to rule out possibilities, and there is a way to do that other than via scientific laws (e.g. [partial] differential equations): by rationality and what he calls the "optimality condition". I can predict the future based on cranking mathematical laws on state, and I can predict the future by knowing what courses of actions agents consider more optimal to achieve their goals.
What you're really fighting here, is an "as if" method of explaining, exemplified by Daniel Dennett's intentional stance. Instead of teleology, you get the appearance of it, built on general causation: teleonomy. That which appears designed actually evolved. You may think you love your significant other, but it's just oxytocin. There are attempts to hide this reduction to general causation (e.g. Sean Carroll's Poetic Naturalism), but it's there.
Libertarian free will, as I understand it, is an attempt to break out of the straight jacket that is general causation, but sometimes (often?) without understanding that the reaction is not to all forms of determinism, but only some of them. A great criticism of what is called 'determinism' can be found in mathematical biologist Robert Rosen's Life Itself. He looks at the specific mathematical forms to which all science was supposed to ultimately reduce—basically, differential and partial differential equations—and argued that it's not even possible to define 'life' with such spartan tools. There are simply more ways that causation can happened, he argued. Were the advocate of libertarian free will to avail himself/herself of this critique, I suspect some interesting progress could be made. Then again, perhaps I am simply ignorant of the latest, best literature on free will.