Simple answer: Creative problem-solving and emergent gameplay.
Long answer:
To create replay value there is one simple thing that a designer must understand: You do not create fun. Players create fun for themselves. You create opportunities for fun.
To be more specific, to me it's all about having multiple ways to approach problems, whether it's the myriad of playstyles in Devil May Cry that come as a result of mixing Dante's weapons, the extensive team-building of Pokemon, or the sheer open-endedness of Metal Gear Solid's various challenges, where they essentially give you the tools to overcome a problem, a starting point, and a goal, and it's entirely up to you to pursue it as you wish. On any given playthrough I don't play MGS3 the same way.
I don't see sheer expansiveness of the environment as a factor here. That does help, and a gigantic sandbox game can eat up a lot of time with sheer dicking around, but I never felt like Fallout or Oblivion had any replay value to them once I got through them that one time; the play-styles aren't different enough and the solution to any given problem or quest is always pretty damn clear-cut, if not patronizingly shoved down your throat.
I have the same problem with a lot of other open-world type games, as well as a lot of the more linear shooters that're coming out now adays. Multiplayer doesn't even make Gears of War interesting to me, because you play it the same no matter who you're with. Find cover, shoot, find better cover, Marcus, flank 'em, rinse, repeat. Engaging problem-solving? Yeah, the first time you do it, but otherwise it's a type of game that's so focused on its cover mechanic that there's practically nothing else to it but the same simple procedures repeated ad nauseum. Co-op gains it exactly one more playthrough for most people I know, and because it's so rigid in the way that it expects you to do things I've never seen anybody play it differently, even when they have vastly different personality types and preferences in gaming.
The mechanics of the game itself have to be broad in themselves so as to present multiple paths to solving a problem, the design of the problems can't force any single solution (RPGs are REALLY bad at this), and there have to be objects in the game that give the player goals that they can set for themselves. These can be clear, intrinsic objects like items they want to get (gotta save up enough rupees in Majora's Mask for the dark milk so that I can have unlimited magic for a few days) or more abstract goals (Mass Effect's dialogue system, where you may want to go all the way to one side or another just to see where the more extreme options take you or so that you can challenge yourself).
Replay value's a pretty damn complex thing when you get down to it. In your case you've got the network flow of the environment going for you, and that's hugely helpful since you can create multiple entry points and paths to different key areas. Focus on that, and try to provide incentive for exploring those different paths.
