It may surprise you to hear that they set cookies (perhaps only for the 'essential' ones) before you grant consent. Check the dev tools of your browser next time you get one of those banners and see what's already lurking.