Sometimes terminology gets in the way of actual meaningful discussion that's useful to gaming. Not that it's bad to discuss terminology, just to keep it in perspective. It's a bit like the whole "what is old school" debate that rears up from time to time with relative meaninglessness.
I don't think it's important to define "sandbox," but I do think it's important to take note of the GAMING points and advice that are raised about the term.
I also (agreeing with others above) think it's about:
1) meaningful choices for players, and
2) the ability for those choices to change the map. If the DM is not willing to see precious city names like "Zthar" get changed into "Jim's Stronghold," then it's not a sandbox.
One point about pre-prepared encounters. They are fine, as long as they are treated like Schroedinger's cat. Here's what I mean. I think it's still a sandbox if the DM has an index card with "Gronk's Orc Horde" statted out on it -- Gronk's Horde is in the status of Schroedinger's Cat. The players keep risking encounters with orc hordes, and might keep avoiding them for a long time. They don't know the risk was Gronk's Horde each and every time. But when contact is made - and the box with the cat is opened - then Gronk's Horde becomes a part of the sandbox and can't teleport about following the players.