Invalidate Internal Page Cache on cookie change
The Internal Page Cache doesn't support cache contexts. It is a simple reverse proxy designed to serve static database content and the only Drupal specific feature it has is to invalidate cache tags. For more dynamic use cases you have to uninstall this module.

The Dynamic Page Cache will then be the frontend cache for anonymous traffic. It is not as fast as the Internal Page Cache, though, so if it doesn't provide the performance you need consider a third-party reverse proxy which is able to handle cookies dynamically.