I think the next step up from a markov chain is throwing the results into https://github.com/languagetool-org/languagetool and checking for grammatical correctness, and retrying each sentence until valid.