my wife are in the outer banks at least once a month - we love it! unfortunately, our '04 runner does not do near as well as our '93 did, but it is still a blast.
few people are probably aware of this but the best spot to mess around down there is north of corrolla.
about a mile north of the beach entrance you will see a tall dune on your left. behind the dune are a bunch of trails that are a blast, although i would recommend severly deflating your tires and having a buddy truck go with you. the only tow truck guy in corrolla is not cheap.