I discovered something interesting recently about Drupal 8 cache contexts—if you have the Internal Page Cache module enabled, some of them won't work.
The way this module works is to cache things based on a key defined in
$cid_parts = [ $request ->getSchemeAndHttpHost() . $request ->getRequestUri(), $request ->getRequestFormat(NULL), ]; $this->cid = implode(':', $cid_parts);
This defines each cache item by its URL (minus the query-string) and format, hence isn't sufficiently granular to separately cache based on cookies.
By disabling this module and relying on the Dynamic Page Cache module instead, contexts like
cookies: will start to work. However, it's recommended to also have another cache in place (such as Varnish) so that you don't end up putting undue load on Drupal.
Hopefully this saves you the time it took me scratching my head to figure this out.