My site only listens to the event after I clear all caches
You need to use a Trusted Redirect Response and properly set cache metadata for your response. This is mostly documented in an answer to a related question, Disabling Page Cache for Redirect Response. However, in your case, you'll need to manually build a CacheableMetadata object, so I'll show that here.
// Tell the browser not to cache the redirect by setting these headers.
$response_headers = [
  'Cache-Control' =&gt; 'no-cache, no-store, must-revalidate',
];

$response = new TrustedRedirectResponse($url, '302', $response_headers);
// We need to add cache metadata to the response so it can be properly cached by
// Drupal. If redirecting was based on a $node or entity, you could simply call
// $response-&gt;addCacheableDependency($node) and addCacheableDependency() would
// automagically pull the correct cache tags, contexts, etc from the object.
// Since your redirect depends on a cookie, you'll have to build a
// \Drupal\Core\Cache\CacheableMetadata object manually.
$cache_metadata = new CacheableMetadata();
// Since you just want to cache the response based on whether they have a cookie
// you can use just the cookies:NAME cache context.
$cache_metadata-&gt;setCacheContexts(['cookies:age_gate_ok']);
// Add the metadata to your response.
$response-&gt;addCacheableDependency($cache_metadata);

$event-&gt;setResponse($response);