Я не являюсь клиентом Verizon, но, насколько я понимаю, Verizon добавляет запрос в тот момент, когда он попадает в их сеть, поэтому вы ничего не можете сделать, чтобы предотвратить добавление отслеживающего cookie на ваш маршрутизатор. (Я подозреваю, что вы можете отказаться от этого зла).
Если вы не можете отказаться от Verizon (я бы предложил отказаться от использования другого интернет-провайдера, если это возможно для вас), лучшим решением может быть использование VPN для обхода захвата Verizons.
Возможно, вам удастся смягчить ущерб, вызванный использованием чего-то вроде HTTP Everywhere, который пытается преобразовать все запросы в HTTPS - я полагаю, что Verizon не может изменить пакеты, отправленные по запросу HTTPS, поэтому, когда сайты используют HTTPS - и благодаря Сноудену многие крупные сайты включают его, это может помочь.