Yes! There was additional incentive for black and mixed race people to move out of Virginia and North Carolina in the early half of the 19th century.
About 8–10% of the black and mixed race population in those two states were "free people of color." Most of them traced their roots as free people to the Colonial era. (Colonial Assemblies passed laws that declared whether a child was free or enslaved based on the mother. Mixed race children with a white mother were "free" by birth. These were usually the children of white indentured women in common-law marriages with enslaved men.) While they were not treated as full equals, they did have far more rights than we might imagine: Some free African American and mixed race men in these states even had the right to vote!
But in the beginning of the 19th century both Virginia and North Carolina began to change their laws and place greater restrictions on free black and mixed race people.
From Paul Heinegg's website, Free African Americans (See: Virginia, North Carolina and South Carolina > Introduction—Free Negro Code):
Many free African American families sold their land in the early nineteenth century and headed west or remained in North Carolina as poor farm laborers. This was probably the consequence of a combination of deteriorating economic conditions and the restrictive "Free Negro Code."
Beginning in 1826 and continuing through the 1850s, North Carolina passed a series of restrictive laws termed the "Free Negro Code" by John Hope Franklin...
Many of those who left the state were enumerated in the 1840–1860 censuses of Indiana, Illinois, Ohio, and Michigan.
So, a number of the men you are researching may never have been enslaved.
Heinegg's website has good lists of names and brief histories for many of the known free families. It might help give you some clues about whether a particular person might be free or previously enslaved.
You might also find free people that came from Tennessee, Kentucky or possibly South Carolina. But conditions and laws were very different in other states. For example, fewer than 1% of the Black people in pre-war Georgia were free. It's probably safe to assume that people from Georgia had been enslaved.