For storefronts, Cool Stuff on Holland Road in Virginia Beach and either of the Replays stores (especially the one on Kempsville Rd) have a great selection. Video Game Heaven is local also and has a lot of stuff from what I have heard (never been to the storefront - only the old flea booth) but the owner wants ebay prices on most things. You may get lucky there tho. I bought all three of my SNES Competition carts there for $10 each.

Hit and miss on the flea of course but Ingram's on Military Hwy in Norfolk and Big Top Flea on Sewells Point Road are usually ok. There is a new location nearby for Bill's Flea Market since the old one burned down a year or so ago but I have not been by there to check it out. Jefferson Flea Market on Jefferson Avenue in Newport News is also ok. I tend to find more DVDs, tools than games but it has a lot of different outdoor sellers every week.