Особенно ярко ратный талант Колдунова раскрылся в 1944 году. Донесения о его победах внешне напоминают эпизоды героических романов или голливудских триллеров, когда не знающий поражений герой уверенно идет от победы к победе. Хотя в данном случае событийная фактура имеет твердое историческое основание: официально Колдунов уничтожил почти полсотни вражеских самолетов, не потеряв ни одной своей машины. Здесь и «охотник», неосторожно «выпавший» на его «як» и с переворота сбитый прямо над командным пунктом, и пара Ме-109, блокировавшая аэродром и прозевавшая возвращение хозяина, и десятки других «шмиттов», «Юнкерсов» и «фокков», сбитых им в Запорожье и под Одессой, над Днестром и Дунаем, в небе Болгарии и Венгрии. Весной 1944 года старшему лейтенанту Колдунову было поручено возглавить четверку прикрытия группы транспортных самолетов Ли-2, доставлявших груз в тыл противника. Над линией фронта транспортники были атакованы двумя восьмерками «штук», не то просмотревших истребителей, не то решивших рискнуть. Неосмотрительная атака стоила немцам пяти машин, две из которых — первую сверху в лоб, вторую снизу и сзади — с резкого боевого разворота сбил Колдунов.
…Когда после майских праздников в 288-ю дивизию прибыл представитель Сопротивления, бывший министр авиации Франции Пьер Кот, человек весьма жесткий и недоверчивый, и попросил показать, как летают молодые, комдив Б. Смирнов остановил свой выбор на Колдунове.
«Перед гостем предстал худощавый высокий пилот в солдатской шинели, — вспоминал Смирнов. — В то время у нас не хватало летного обмундирования, и Колдунов, прямо скажем, не смотрелся. Рукава шинели чуть ли не по локоть, кирзовые сапоги с короткими голенищами. Колдунов взлетел. Через несколько минут он появился над командным пунктом. На высоте двадцати метров на большой скорости он перевернул самолет «на спину», пролетел над всем аэродромом вниз головой и затем на минимально допустимой высоте исполнил динамичный каскад фигур высшего пилотажа. Бывший министр был в восторге: «Вот это солдат! Вот это летчик!»
В конце лета 1944 года Александру Ивановичу был передан именной Як-3 с надписью: «От колхозника Богаченко Г. А.». На этой машине он воевал до последнего дня, позднее она была передана румынскому правительству по его просьбе и находилась в Бухарестском доме пионеров.
7 ноября 1944 года союзники решили сделать «подарок» и группой в 50–60 самолетов у югославского города Ниш подвергли штурмовке находящуюся на марше колонну 37-й армии. Советские войска понесли потери в живой силе и технике, был убит генерал Г. Котов. Восьмерка Колдунова была вынуждена вступить в бой с американцами, тем более что часть их самолетов пыталась блокировать аэродром и сбила два взлетающих «яка». В первой же атаке советские летчики сбили три «лайтинга», а Колдунов, пройдя сквозь паутину трасс, сблизился с ведущим союзников на несколько метров. То ли тот разглядел наконец красные звезды, то ли его впечатлила пушечная очередь «яка», сверкнувшая над самой кабиной, то ли понял немудреный жест, каким приветствовал его советский летчик, но штурмовка была прекращена. Позднее американская сторона принесла извинения за инцидент, выразила соболезнования по поводу погибших. Сбитых, конечно, не записали никому, но однополчане видели, что одного из них, особенно увлекшегося расстрелом колонны с бреющею полета, сбил Колдунов.
8 декабря 1944 года капитан Колдунов «достал» немецкого разведчика в районе Дунайских переправ. Противник, записанный как Ю-88 (по-видимому, Ю-188), применил весь комплекс оборонительных средств: заградительный огонь стрелков и воздушные гранаты, маскировку в облаках и дымовую завесу, резкое пикирование и полет на предельно малой высоте.
Зимой 1944/45 гг. Колдунов продолжил список побед в боях над Венгрией, за три месяца сбив 15 неприятельских самолетов.
В феврале 1945 года он возглавил «группу по расчистке воздуха», куда входили капитаны Шишов и Сидоренко, Сурнев и Гурьев, лейтенант Шамонов, с 1944 года постоянный ведомый Колдунова (совершил около 300 боевых вылетов, лично сбил 9 и в группе 4 самолета противника). Великолепная шестерка сбила 32 самолета противника и не имела потерь.
Свои последние победы советский ас одержал западнее Вены, сбив двух длинноносых «фоккеров» — Та-152.
В 1952 году он окончил ВВА. Командовал авиаполком, дивизией. С 1960 года, после окончания Военной академии Генштаба, служил заместителем, а позднее — командующим ВВС Бакинского ВО. Генерал-лейтенант авиации Колдунов летал до 1965 года на реактивных и сверхзвуковых боевых машинах (МиГ-19, Су-9, МиГ-21). Лауреат Ленинской премии (1984). В конце 60-х годов Колдунов служил на Дальнем Востоке, а с 1970 года — командовал ВВС МВО. В 1975 году генерал-полковник авиации Колдунов был назначен первым замом, а в 1978 году — главкомом войск ПВО, заместителем министра обороны СССР. В 1984 году ему было присвоено звание Главного маршала авиации.