Could not find a valid session key when submitting opt out and unsubscribe forms
Check that your webserver serves correct cache headers when accessing the unsubscribe URL. It sounds like CloudFlare is caching the forms your CiviCRM install generates, and so a later anonymous visitor is seeing an expired form. 

While CloudFlare offers additional ways to customise what gets cached, using standard HTTP cache headers is your best bet because it works the same for CloudFlare and other caches your userbase might encounter (ISPs, corporate proxies, whatever).

By default CiviCRM seems to set appropriate cache headers which tell CloudFlare not to cache forms, including unsubscribe forms.

Let's see if CiviCRM sets cache headers suitably on an unsubscribe form. I searched my email for civicrm/mailing/unsubscribe to find an example URL.

Fetch just the page headers using curl -

$ curl --head "http://example.org/civicrm/mailing/unsubscribe?reset=1&amp;jid=XXX&amp;qid=XXX&amp;h=XXXXXXXXXXXX"


And check that you see headers in the response that should prevent CloudFlare caching that page:

HTTP/1.1 200 OK
Server: nginx/1.6.3
Date: Tue, 13 Oct 2015 18:08:55 GMT
Content-Type: text/html
Connection: keep-alive
Vary: Accept-Encoding
Expires: Sun, 19 Nov 1978 05:00:00 GMT
Cache-Control: no-cache, must-revalidate, post-check=0, pre-check=0
X-Micro-Cache: MISS


The interesting headers here are Expires (in the past) and Cache-Control (no-cache).

You can compare those results to headers returned by your CiviCRM site for a similar request. Test using the URL that connects directly to your site, not using the CloudFlare URL, and confirm that appropriate cache headers will be set for requests to those URLs on your server.

It might be that you have some other customisation or module which changes the cache headers for CiviCRM URLs, and that would then lead CloudFlare to believe that the forms should be cached.

FWIW, we use CloudFlare on a few sites, and have no custom page rules in place; as far as I know it's worked with no special tweaks.