В данном случае сочетание не спеша можно считать наречием.

Не спеша может выступать в зависимости от контекста и наречием, и деепричастием. Как деепричастие не спеша пишется раздельно согласно правилу раздельного написания НЕ с деепричастиями. Написание не спеша как наречия проверяется в словарном порядке. Среди наречий есть значительное количество единиц, традиционное раздельное написание которых не соответствует частным правилам написания наречий.

Сочетание не спеша всегда нужно писать раздельно. В орфографических словарях, начиная со второй половины ХХ века, рекомендовалось только раздельное написание. В толковом словаре под ред. Д. Н. Ушакова (1935—1940) и в Большом академическом словаре (1948—1965) фиксируется сочетание не спеша.

В обоих случаях ставится запятая. Не спеша - наречие.

Оба варианта верны.

В предложении о разведчиках формально верен второй вариант. Но это предложение построено неудачно. Деепричастный оборот, отрывающий причастие от зависимого слова, затрудняет чтение, мешает восприятию смысла. Предложение нужно перестроить.

В предложении про грачей сочетание не спеша обособлять не нужно.

Сочетание не спеша представляет собой пограничное явление. По форме это деепричастие, по функции — наречие. Как наречие не спеша охарактеризовано в «Русской грамматике» 1980 г. В правилах орфографии оно часто включается в перечень деепричастий (как форма глагола):

Отрицание не пишется раздельно в следующих случаях.

1. Со всеми формами глаголов (кроме полных причастий; о них см. § 150):

а) с инфинитивом и спрягаемыми формами, напр.: не знать, не знаю, не знаете, не знал, не знали, не торопишься, не торопимся, не торопись, не нравится, не повезло;

б) с краткими формами причастий, напр.: не использован, не накрахмалено, не откупорена, не разработаны, не закрыто, не занят, не выпито;

в) с деепричастиями, напр.: не желая, не отвлекаясь, не спеша, не шутя, не успев, не встретившись.

(Правила русской орфографии и пунктуации. Полный академический справочник / под ред. В. В. Лопатина. М. Любое издание)

Да, существует такое деепричастие (форма глагола спешить).