Не все, конечно, подобно Ермолову, умели ценить эту энергичную и плодотворную деятельность Мадатова. На самую память его брошено несколько жестких обвинений, в которых ему не пришлось найти всеобщего оправдания, хотя, конечно, и были люди, лучше понимавшие его и его положение. Следя за его управлением татарскими провинциями, многие и при жизни его и после находили в его действиях нечто азиатское, произвольное и деспотичное, от чего будто бы он сам, уроженец Азии, воспринявший с детства все политические и общественные понятия ее, не мог отрешиться в течение всей своей жизни. Что в его действиях был этот характер,– оспаривать никто не будет; но ему есть другое, более веское и логическое объяснение. Нужно представить себе этот край, в котором ничто не уважается, кроме силы и власти, край, только что перешедший из рук ханского произвола под господство закона и не утративший ни одной черты в понятиях, которыми объяснялась и поддерживалась деспотичная власть, чтобы понять, что Мадатов, коротко его знавший, только приноравливался к его обычаям и нравам. Так, чтобы вызвать необходимое обаяние своей власти, он, как рассказывают, донося о всех предположенных им смертных приговорах, вместе с тем всегда представлял народу дело в таком свете, что он своей властью казнит и имеет на то право; и это было целесообразно с нравами и понятиями мусульман. Не нужно, притом, забывать и другой стороны деятельности его, той, что знание края давало ему постоянную возможность исправлять ошибки других. “Справедливость,– говорит один из современников Мадатова, бывший вместе с ним позже в Турции,– может быть достигнута только сравнением того, что совершил князь, с тем, чего не сделали или что испортили другие... Грузия была свидетельницей того же, что происходило на моих глазах в Турции. Делались огромные ошибки; князь исправлял их, и в то время, когда им уже были сорваны лавры, являлись распоряжения, мешавшие ему доплести из них венок...”
Падение Ермолова увлекло за собой и его любимого сподвижника. Мадатов сошел со сцены кавказской войны не обиженным только, но глубоко и несправедливо оскорбленным. Имение в Карабаге, оставленное за ним высочайшей волей не без политических расчетов, послужило для Паскевича главным предлогом к его обвинению и создало нарекания, мрачной тенью отразившиеся не только на нем, но и на самом Ермолове,– честность которого уже отмечена историей.
В тягостном и непривычном бездействии пробыл Мадатов в Тифлисе целые пять месяцев. Наконец, через Дибича ему удалось добиться позволения приехать в Петербург. В то время шли уже приготовления к турецкой войне, и Мадатов был прикомандирован к третьему пехотному корпусу, входившему в состав действующей армии. Там, на Дунае, с небольшим отрядом он овладел двумя турецкими крепостями, Исакчей и Гирсовым, и отстоял селение Проводы, расположенное у подошвы Балкан. “Ура! Любезный князь,– писал ему граф Воронцов из-под Варны,– я знал, что герой Дагестана будет героем и в Балканских горах”. Четырнадцать знамен и девяносто восемь орудий были трофеями Мадатова в эту кампанию. И несмотря на все это, неблаговоление Паскевича так сильно отражалось на службе его, что Мадатов за весь этот поход получил только одно “монаршее благоволение”. Наконец, уже в начале 1829 года, он был назначен начальником третьей гусарской дивизии. И вот, на тех самых полях, на которых за двадцать лет перед тем Мадатов получил георгиевский крест, теперь пришлось ему встретиться опять с александрийцами, уже входившими в состав его дивизии. “Ну, слава Богу,– шутил он с гусарами,– мы опять увидим турок. Только вы, братцы, их всех не рубите; за пленных дают по червонцу – сгодится, а лошадей их мы маркитантам за долг отдадим”. И гусары восторженно глядели на того, чье имя давно уже тесно связалось с их полковой славой.