I think the key concept for a sandbox is player freedom at the 'choosing the adventure' level. A GM could present linear adventures in a sandbox campaign but that wouldn't stop it being a sandbox, assuming the PCs were free to leave adventure A and go on adventure B, C or D instead. It gets tricky if there's some device like a portcullis at the start that traps the PCs in a linear dungeon. One could argue that at that point the game is no longer a sandbox.
By this definition, an adventure path must be the opposite of a sandbox, assuming the AP is being run exactly as presented. A GM could of course take an AP and turn it into a sandbox by adding lots of additional adventures. This would be very much like the Fallout 3 or Oblivion crpgs which both have 'main quests', but are definitely sandbox games because of the great number of 'side quests', the player's freedom to wander, and because the main quest can be abandoned and returned to at any time.
Even games as massive as Fallout 3 and Oblivion have limitations on player freedom. They are set in a finite area in which there are only a finite number of quests. I think that for a traditional sandbox such as The Vault of Larin Karr, the GM does need the player's agreement not to leave the 'adventure area'. Or to give him a chance to buy/create a new area if they do. This is mentioned in the West Marches website linked to above.
The sorts of game that Mallus is talking about are a bit different than Vault of Larin Karr, the West Marches, or the example I gave. The players have lots of freedom, but there are also plots and the environment is non-static. You could still call this a sandbox, but it's of a somewhat different kind, it's not a traditional static location-based D&D sandbox.