Good question.
First of all, I'd like to respectfully ask Derren to exit the thread. There are lots of other threads that are devoted to picking apart the pros and cons of 3e vs 4e, and I feel that your discussion has moved into that arena. Thank you for the insights that you gave up-thread re: 3e and sandbox games, but at this point, I think both sides of the argument have said all that needs to be said in that vein.
I'm still pretty torn, but I think it's going to come down to when my players want to play. If they want to play now, we'll do 3.5e. In many ways, that's more attractive to me, because I'm itching to run and we know the rules so well that I can concentrate on other things. However, the prep time thing... that's going to be a pain once the PCs hit 4th level and up. Otoh, I've got piles and piles of maps, encounters and other junk lying around for 3.5e I can use.
By the way, to clarify how I'm planning on running this sandbox: I'm not going to scale encounters. My map has ELs for each area, roughly by travel time. So the hexes right near the keep (our home base) are EL 0-1, and the further away you travel, the higher they get. I mostly do it by terrain, so the ELs are more gradual along roads, rivers and other easy terrain where the PCs can travel quickly. Mountains, forests and swamps get harder faster.
Locations in the different hexes start at the given EL and go up as you get deeper inside (they're all pretty much dungeons). The player map has some named areas filled in and some known locations, along with a brief description of each. Mostly things like "goblin territory" or "no one put ashore ever returned". I've also got some hot spots, where there's a really tough location in the middle of a relatively low-level area. These tough locations are also known by rumor.
Similarly, the tough locations have monsters that won't pursue or otherwise venture into the low level surrounding area.
One thing that I'm still working out is the role of quests. I'll likely have some minor quests: hunting down outlaws, delivering things to various barbarian tribes, the fur trade. Beyond that I don't know. My goal is to write up a general history of the area that explains why it's all wilderness and ruins. Through exploring, I'd like players to be able to discover new locations, figure out how to get to inaccessible places, and dig up information about what they might find there.
I'm hoping my prep will be relatively low. Players have to tell me where they're going before the session starts, so I plan on rolling for random overland encounters beforehand, and statting out what I expect them to get to. With luck, I'll be able to re-use those encounters as parties return to an area multiple times. I'm really not worried about TPKs. If they happen... well, now the players know that's a dangerous area.
I'm not the kind of DM who worries about meta-game knowledge. Who knows how the next batch of PCs heard about the TPK? Maybe the barbarians who trade with the goblin-king heard the story...
Anyway, I'll keep you guys posted. Thanks a lot for the advice. If you get any more insights, please let me know. It's my first sandbox game, so I'm sure there are gotchas I haven't anticipated.