Baggins,
I'm a little surprised none of the Richmond or Norfolk guys responded to you. I'm a couple of hours north, but my impression is that it's tough to get permissions in those areas. Lots of history in the ground around there...
Check the thread about detecting laws in Virginia. There is a lot of confusion about where or whether hunting is allowed on "public property". I've been in touch with local officials in my area (Fairfax County) and been told hunting for and/or removal of relics from publicly owned land is prohibited. For that reason, I hunt private land with permission almost exclusively.
Check with the people you'll be working with. I'm sure someone knows someone who has property.
Sorry I can't be more help.
Good luck,
DCMatt