I am very familiar with the area that you describe. That area is immediately to the west of Ft. Smith Arkansas where I grew up. Ft. Coffee is one of the historically black towns. The area still exists as a small settlement west of Ft. Smith.
The town of Skullyville no longers exists however the cemetery is still there. The closest town to the cemetery is Spiro Oklahoma. I have visited that cemetery in hopes of learning about the numbers of slaves buried there. The north side of the cemetery is where the slaves and former slaves are buried.
What are the names of some of your ancestors? I have the final rolls and the index to the Choctaw Freedmen and will be happy to take a look for you to see what records their may also be for you.
[10 Nov 1999]