Hm. Take a look back at the OP for a moment. "What elements must be present in a game for it to be a sandbox?" Looking for definition by inclusion.
Much of the following discussion has been definition by exclusion - looking for things that make something "not a sandbox".
If it looks like a duck, walks like a duck, and quacks like a duck, it is a duck. If the thing also has lasers, that doesn't make it not a duck. It is just a duck with frikkin' lasers.
One can take the question one step further - What can a GM do to foster and use player-direction?
There are different levels of player direction. Most of those levels make the game not-a-sandbox.
No player interaction -- no game. The players are essentially listening to narration
Player interaction through tactical control of characters is a static universe -- heroquest or equivalent board game.
Player interaction through character control limited by DM/OOG constraints -- not a sandbox. This limitation can be a "you don't do that", automatic failure, a railroad track, or the refusal to present any other opportunities to the group until the current one is dealt with.
Player interaction through character limited only by environmental constraints -- may be a sandbox depending on how the DM prepares and presents material for interaction
Player interaction through character control and collaborative imput into world design -- not a sandbox
Player interaction through shared story-telling and narrative control -- collaborative storytelling.
At least as fundamental is how the DM prepares the material for the environment. I think there are a few telling signs the DM can check to see if he is prepared to sandbox.
- Is the DM willing to live with the campaign consequence of any plot being ignored / refused / undermined?
- Is the DM willing to present the material to the group and abide by their choices as they affect the game world regardless of a preferred outcome?
- Is the DM willing to place any behavioural / action constraints expected of the players into the game environment?
- Is the DM willing to examine the actions of the PCs and have the environment react?
I think sandboxes work best as status quo universes, but I'm uncertain that that is a actual requirement.