Intermittent, ambiguous error "requires cookies" or is it "invalid session keys"?

Fresh, clean install of Drupal 7.61 + CiviCRM 5.7.0 on PHP 7.1

Error is intermittent (maybe every 3rd or so time) when editing contact records like adding a phone number (inline or record save) or clearing caches. Likely other actions trigger the error as well but these are the ones we've discovered so far.

HTTPS is enforced in .htaccess and permanent redirects in place to ensure one URL is used.

No javascript or network console errors. No related apache server errors logged.

The CiviCRM error message is vague and makes little sense. Cookies are enabled in the browser. And is it a cookies or invalid session key issue? It's very strange that it isn't triggered consistently, every time.