UPD:
Значит ситуация оказалась совершенно не такой, как казалось на первый взгляд. После создания вопроса я собрал много дампов траффика для выявления к них аномалий приводящих к таковым последствиям. Так же гораздо глубже познакомился тем, как работает CEF и тд.
В результате чего, было выявлено, что CEF не имеет прямого отношения к данной проблеме, точнее, его поведение закономерно и правильно.
В результате анализа я выявил, что проблема характерна только для фреймов длинною в 81 байт. Более того, если фреймы содержали IP payload, с UDP payload, который в свою очередь содержал DNS payload, в котором содержался запрос на резолв доменных имён длинною в 21 символ. Точнее, размер итогового фрейма является следствием того, что доменное имя имеет длинну 21 символ. Тут нужно сделать заметку, что в случае, если DNS resolver использует дополнительные поля в DNS пакете, то длинна пакета будет больше и фрейм выйдет за границу в 81 байт, но в случае с Windows DNS он будет именно таким.
Дальше больше, ISP использует в качестве последней мили 802.16 WiMAX, в итоге схема подключения выглядит так Edge Router -> ISP Switch -> WiMAX AP -> WiMAX AP -> Some Devices -> CISCO ISG Router.
Так вот, радиорелейный тракт и был причиной данного поведения, к сожалению ISP отказался пролить свет на ситуацию, что тому было причиной, но спустя неделю переписки с Москвой, теперь техническая поддержка для Сибири там, будь проклят тот день, когда они сделали это, провайдер не смог найти нечего лучше, чем просто сделать полный перемонтаж их радиорелейного тракта.
Название провайдера я называть не буду, но это крупный ISP по меркам России, говорить о том, что не одного инженера NOC я так и не услышал я думаю не стоит, люди на том конце, к сожалению даже не могли открыть дамп, чтобы удостоверится, что то, что я говорю правда.