Oh, I've tracked John year by year looking for Sarah. Here's what I've done already:

Sarah appears in Lancaster, VA, in 1850. There is no digital version of the city directory before 1923 (maybe I should be making microfilm requests for the Lancaster city directories of the time)

John L and family are in the 1870 US Census in Charleston, SC. This census doesn't list the address, however...

The Charleston city directory in 1869 lists his address as "27 Queen." Sarah is not in the household, though (she doesn't appear under Lunsford, and scanning the directory for the address doesn't turn up anyone else).

By the city directory in 1875, John's address is listed as "16 Coming". (No Sarah) John's son John first appears in the directory as well, same address.

Next directory, 1877, he's moved to "23 Society". (no Sarah) Same address in 1878 & 1879 directories. (No Sarah).

Sarah finally appears in the household in the 1880 census -- but John no longer appears in the city directory of this year. A quick scan of the address shows new people living at the address.

1885, John's son John started showing up in the personals in a Waco, TX, newspaper.

1886, John re-appears in the Waco, TX, city directory. (No Sarah) This is the first year available for the city directory in Waco, TX, so it's possible the family moved here as early as 1880.

The 1890 census was lost to fire, but John still appears in the city directory of that year.