My default setting has always been a sandbox since the earliest days and it seems to work just fine in 4e. I've fiddled around a bit with the best way to make things work, but basically the approach is pretty much the same as I used in 2e.
Every area is designated with a level. I generally just tend to use 1, 6, 11, 15, etc as it isn't profitable to get less coarse than that. Areas can be any size. Some are large, some are small, all of them are cohesive and reasonably well bounded. Regions far from the focus of the action tend to be large and scantily detailed but serve as destinations for quests etc. The areas near the focus obviously are a lot more detailed and can be quite small, maybe even a specific ruin or something like that.
Every area has lore. Usually it is best to have 2 sources of lore for each one. The more important and obvious areas are usually pretty easy to find lore for and it generally makes it pretty clear what level of area it is. More specific lore may exist as well if the PCs want to go find it. Most areas also have plot hooks. This means it is pretty hard for the players to just blunder into things. Often if they come on/enter an area they can get at least some idea of what to expect there, or they can go do some research etc and find out. Unless they're pig-headed about it they will rarely enter areas outside their competency.
I have found that 4e is no worse than any other edition as far as providing hooks and motivations. Magic items aren't technically quite as huge a motivation perhaps as they were in AD&D, but really aren't that much less either. Some areas might be associated with artifacts, others are the likely (and usually only) sources of specific valuable items like say a Staff of Ruin or Iron Armbands of Power. Most players like having those things and will certainly go after them, especially when they really can't get them elsewhere. Perhaps they can make lower level versions, but the group rarely has enough treasure to do a lot of crafting.
As far as higher level challenges being potentially grindy there are a few ways to avoid that. One is to generally have a few lower level challenges in the area that they'll run into first. Once the party finds the DOORMAN of the Giant Castle to be a significant challenge they're not too likely to blunder on in further and run into the Giant himself. If they do, then you really just have to make it an interesting encounter with fun terrain etc. Provide ways to defeat monsters without grinding through all their hit points every time, or else make it perfectly clear that they might want to escape. If they go after a lot higher level area I've found 4e is a lot more likely to let you actually get away than AD&D was. At least you have a buffer of hit points and surges to keep you up long enough to think about it. In AD&D you were usually dead by the time you realized you were totally outclassed, except the poor fighter, who had pretty close to no way to exit stage left...
I've never had the 15 minute adventuring day problem except in one dungeon crawl area. It is true that PCs may decide to hole up after a random encounter, but even a modicum of logic and story generally kills that option in fixed encounter areas. If the PCs stir up the orc lair they darn well better teach the orcs to leave them alone or clean them out entirely because the nearby village is going to be down in flames if they don't! If you start something, you pretty much want to finish it and trouble will find you fast if you don't. Anyway there are plenty of other tried and true ways to lead parties on, just don't overuse one of them too much.
Although I do have some mini-areas that are just a couple of encounters ALMOST all major locations have plot significance. It is up to the players if they want to engage in a particular plot but the world isn't going to just sit still for them, so they need to make up their minds and get on with it in most cases.
As far as skill checks go, just determine from the area the PCs are in what makes sense. That doesn't handle everything, but my approach is that there's no point in making easy mundane checks anyway in most situations. When I establish the difficulty of an action I'll note it, so i know that climbing trees is a moderate level 1 Athletics check usually. Maybe in a higher level area there may be bigger trees, but generally there will be cliffs or whatever that are more interesting for those PCs to climb. It mostly works out fine.
As someone noted above 4e does let you restrict movement a lot more easily than AD&D did, so you can keep areas out of general circulation for lower level characters.
I agree that PoL works GREAT for a sandbox and not surprisingly I've always used a PoL type of setting. It makes it much easier to carry threat levels on up to high levels. Anything can be out there, and the fact that it hasn't YET overrun the local point of light doesn't mean it won't be an epic threat tomorrow.
