FYI, Google admitted there is a sandbox. Can't be a myth if they acknowledge it. Now what exactly is the sandbox is another debate entirely.
The quotes I've seen from Matt Cutts at Google are:
"There are some things in the algorithm that may be perceived as a sandbox that doesn't apply to all industries"
and
"In reply to a question from Brett Tabke, Matt said that there wasn't a sandbox, but the algorithm might affect some sites, under some circumstances, in a way that a webmaster would perceive as being sandboxed"
That's a bit different from saying Google acknowledges the sandbox. When talk of the sandbox first took hold, many people thought that all new webpages (or websites or webdomains, depending on your point of view) would automatically be placed in the sandbox for a period of some months. Nowadays, people say that it depends on what keywords you're targeting.
The Matt Cutts quote above specifically talks about it affecting "some sites under certain circumstances". I think this is much more likely to be related to suspect link-building, and the way Google detects unnatural growth in links, and holds back on realising full PR for those links until the site has had a chance to prove itself.
This is quite separate from being penalised in the Google rankings, which is the effect that many connect with the sandbox. In other words, if link building is done carefully, at a sensible rate, and you carry out plenty of on-page optimisation (the part that often gets overlooked), there's no reason I know of that menas your page can't rank well within a few weeks or months of being indexed.
Howard