Don't forget to check the Special Nottoway Indian Census of 1808. If you need a link, let me know. You won't find it on Ancestry.com. Although this census was to enumerate the Nottoway Indians in Southampton County, you will see surnames that surface around this time. Around the late 1700's is when the Native Americans in Southampton and surrounding counties started using English sounding surnames. Most of the Nottoway and Nansemonds married into White or Black families. It is reasonable to assume that there were quite a few free blacks or free persons of color (mulatto) in Southampton county. The Nottoways and Nansemonds were pretty much wiped out by what I call the white man's 3 D's...death, disease, and destruction, so they had to marry into white or black families. I've been lucky enough to find my Southampton County ancestors due to well documented paper trails.
In addition check the census records for Hertford and Bertie counties in North Carolina. Alot of families from Southampton County migrated south to these counties. Northampton County, NC also had a very large population of free blacks or free persons of color. I would check the census records for this county as well.
If you can get your hands on property and tax records, this will be a great help as well. The online records for certain counties will only go back a few decades of course. I think Southampton County's online records only go back to the 1980's, so you may have to take a visit to the courthouse to get land deeds/records for anything prior to 1980.
Have fun and good luck!