Gating choices is exactly what I described in my post.Okay. I'll accept that definition for the sake of argument.
That means that unless the DM puts high level monsters in that area with the intent of altering or limiting their choices, it's still a sandbox.
One way a DM might do this is through organic world creation. Some areas have ecosystems that have a higher average CR than others. For example, a kingdom of the giants. No intent to limit the players is involved, but rather the DM considers what makes sense in a giant kingdom (giants, dire animals, etc). This may limit the players in effect, but not because the DM intended to do so, hence it does not violate the definition of sandbox that you quoted.
Personally, though, I think you can absolutely design a sandbox to be gated. That might involve making certain areas higher CR, or simply involving barriers that a low level party cannot overcome (exploring the sunken city of Atlantis is largely impossible until you have some means of water breathing). I don't think that intentional gating means that a game isn't a sandbox. IMO, it's only truly linear if the players come up with a clever solution to bypass the gate, but the DM heavy-handedly prevents them from passing the gate anyway.
One of my favorite styles of sandbox is what I think of as Linear Sandboxes. This consists of a number of relatively small sandboxes (perhaps around 100 square miles each). There's an overarching goal of progression, but otherwise the players are completely free to do as they desire.
In one example of this style of campaign, our world had died. The cycle of rebirth required heroes to undergo a trial which involved traveling through the memories of the planet and collect the souls of unborn gods. Collecting all of the souls in a memory would allow passage to the next memory. Ultimately, if the heroes were able to overcome the trial, the gods would be born and renew the world (and also grant each hero a boon). It's very linear in one sense (the arc of the campaign), yet each memory was completely non-linear. We even threw the DM for a loop when we caused a temporal paradox that he completely didn't expect (but he handled it with aplomb and didn't try to railroad us at all).