Злые языки в то время рассказывали, что фельдъегерь, который схватил Коцебу, известного драматического писателя, на границе и отвез его в Сибирь, как раз и был этот самый Шульгин. Коцебу впоследствии называл его только по фамилии и говорил, что он отличался курьезной способностью пить и есть на каждой станции при перемене лошадей — без разбора и порядка, все, что можно было отыскать, — мед и паюсную икру в одно и то же время».
А в записках Михаила Шевлякова, составленных по рассказам начальника Санкт-Петербургской сыскной полиции И. Д. Путилина приводится следующая веселая история о нем:
Искоренение воровства
Московский обер-полицмейстер А. А. Шульгин был назначен на эту должность специально, как ходили в то время слухи, для искоренения мошенничества и воровства.
Приехав в Москву, Шульгин громогласно хвастал, что искоренит это зло, и принялся за него не на шутку. Но московские жулики, проведавшие об этом, на первых порах его деятельности заявили себя необоримыми и дали о себе чувствительное понятие самому новому обер-полицмейстеру.
Рано утром подъезжают к дому обер-полицмейстера парные сани с ливрейным лакеем. Ливрейный лакей, лихо соскочив с запяток, входит в швейцарскую и приказывает доложить Шульгину, что за ним приехали сани от графини Орловой, которая просит его пожаловать к ней сейчас же по неотложному и весьма важному делу.
Шульгин, лично знакомый с графиней, быстро собрался, накинул на плечи свою богатую бобровую шинель и отправился. Приехав к графине, обер-полицмейстер вошел в подъезд и сбросил на руки сопровождавшего его лакея шинель. Лакей почтительно принял ее и присел на скамейке в прихожей. О Шульгине доложили хозяйке дома.
— Чем могу служить? — спросил гость, входя в гостиную и раскланиваясь с графиней.
Та недоумевает.
— Вы сейчас изволили прислать за мной свой экипаж, — сказал Шульгин, в свою очередь тоже недоумевая.
— И не думала!
— Я в ваших санях приехал.
— Не может быть.
Подняли в доме тревогу. Бросились к подъезду за санями, но их и след простыл.
На другой день Шульгин получает по почте безымянное письмо, в котором между прочим говори лось: «Напрасно вы, ваше превосходительство, с нами ссориться хотите, будем жить лучше в мире да ладе, никто из нас не будет внакладе».
Это обстоятельство сперва обескуражило его, но впоследствии он уяснил смысл письма как нельзя лучше: жулики посвящали его во многие их тайны, что дало ему возможность в особенно важных делах проявлять необыкновенное проворство и ловкость к открытию преступлений. Этим он прославился как деятельный обер-полицмейстер.
