Sporadic error: Could not find a valid session key

We are sporadically seeing this error on contribution (donate) pages. Cookies are working. In fact, the error goes away if we clear cookies from the browser. Could it be a stale session ID in the browser? or some other problem with the session?

"Sorry. A non-recoverable error has occurred.
We can't load the requested web page. This page requires cookies to be enabled in your browser settings. Please check this setting and enable cookies (if they are not enabled). Then try again. If this error persists, contact the site adminstrator for assistance.

Site Administrators: This error may indicate that users are accessing this page using a domain or URL other than the configured Base URL. EXAMPLE: Base URL is http://example.org, but some users are accessing the page via http://www.example.org or a domain alias like http://myotherexample.org.

Error type: Could not find a valid session key.

Return to home page."