Your very close in being correct, the first postmaster(Choctaw Nation)was
Gary E. Scales date of appointment Sept. 18,1857, Toboxky.
I noted that no place called 'PERRYVILLE' on any P.O. or known written records until after the war.
Likely this was Scalesville on the mail route,it also had a court house.But soon forgotten
after the town was burned, remembered only by the living Perry's who name attacted it to name "Perryville" to this ghost town it name lost.
Writters keep this town-name-alive
The many of the Perry's lived on,-- the 'old' town did not.
One of my Gf was a Frank Perry who lived there and was from one of these clans.