I wonder if that code is in a embedded snippet.. Couch does cache snippets separately in db.
Good point. Not an embedded snippet.
To simplify the parameters of the issue, I did a test removing the complicating factor of using a query string in the URL and evaluating it with PHP to "turn on" randomization. Instead, I went ahead and just hard-coded orderby='random' directly into the <cms:pages> tag, then tested the page again. It's still the same issue: the blog post order randomizes only the first time, then stays the same until some kind of session expiry type of time period passes.