Семья Генри не оставляла надежды вытащить его из тюрьмы, благо он вел себя там примерно. Его матери удалось встретиться с президентом США Теодором Рузвельтом и рассказать ему о судьбе сына. Не забыла она упомянуть и о помощи, оказанной им правосудию при попытке бегства Кроуфорда Голдсби. Рузвельт, трепетно относившийся ко всему, связанному с историей Дикого Запада, обещал помочь. Он лично позвонил в тюрьму и спросил Генри, как тот намеревается жить, если его выпустят на свободу. Старр ответил, что его криминальная карьера закончена и он не хочет к ней возвращаться, твердо решив начать честную жизнь. Они говорили долго, и бывший грабитель сумел произвести на Рузвельта хорошее впечатление. Президент подписал бумаги о помиловании, и в январе 1903 года Старр был освобожден из-под стражи.

Судья Исаак Паркер очень любил отправлять людей на виселицу, отчего и заслужил прозвище Вешающий судья

Сперва Генри действительно пытался жить честно. Он женился, обзавелся ребенком, которого в честь президента назвал Теодором Рузвельтом. Неизвестно, как бы сложилась его дальнейшая судьба, если бы спустя пять лет он не встретил своего старого друга и компаньона Кида Уилсона. Они недолго сопротивлялись желанию вспомнить прошлое, и 13 марта 1908 года ограбили на 2500 долларов банк в городе Тайро, штат Канзас.

Первыми грабителей нагнали люди из Тайро. Они уже решили, что окружили бандитов, но сильно ошиблись. Выстрелы по ним раздались совсем с другой стороны. Бандиты подстрелили двух лошадей, помахали незадачливым преследователям шляпами и ружьями, после чего скрылись. Они явно не хотели никого убивать.

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

Ситуация в округе накалялась, нервы у многочисленных преследователей были на пределе. Люди из Тайро ехали в сторону Ванна, когда раненый маршал Ли вдруг обнаружил, что потерял на холме свою записную книжку, и послал за ней одного из местных. Увидев его, люди из Тайро приняли беднягу за бандита и начали палить по нему из всех ружей. Человек помахал им руками, пытаясь показать, что он друг, в ответ стали стрелять еще яростнее. Бедняга решил не испытывать судьбу и развернул коня, но чуть позже наткнулся на другого жителя Ванна, ехавшего на легкой двухколесной коляске. Этот тоже не распознал его и открыл огонь. Посланник маршала больше не хотел рисковать жизнью ради записной книжки и вернулся в город ни с чем.

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

Погоня из города Очелата состояла из четырех человек, прихвативших с собой свору охотничьих собак. Неожиданно метрах в ста от них показался человек. Он размахивал руками, показывая, чтобы они не приближались. Человек оказался поваром из лагеря разработчиков нефтяных месторождений. Незадолго до этого бандиты подъехали к его палатке и велели ему приготовить им обед. Заметив приближавшихся людей, повар попытался предупредить их об опасности. Но преследователи поняли его жесты только после того, как из кустов вышел Генри Старр с направленным на них ружьем. Глядя на поднявших руки людей, повар с сожалением пожал плечами.

— Что вам, парни, надо? — Старр говорил спокойно, но в голосе его звучали металлические нотки.

— Мы, это… — констебль Дэниелс указал на свору собак и их хозяина, на боку которого висел охотничий рог. — Охотились на волков и теперь никак не можем отыскать моего короткохвостого пса. Не видели его, а?

— К черту тебя и твоего короткохвостого пса, — Старр разозлился. — Вы меня ищете, и не надо мне врать.

По его приказу второй бандит отобрал у горе-преследователей все оружие и разбил его о камни. Издеваясь, он вернул искореженные револьверы и ружья владельцам. Грабители не стали убивать «охотников». Они поменяли своих измученных лошадей на свежих скакунов законников, взяли приготовленный поваром обед и уехали.

В тот раз грабителей так и не смогли поймать, однако Дэниелс узнал в них Генри Старра и Кида Уилсона. Вскоре друзья ограбили еще один банк в Эмити, после чего Уилсон решил завязать с криминалом. Больше о нем никто никогда не слышал. Генри повезло меньше. Он попался в Аризоне и был выдворен в Колорадо. В мае 1909 года там состоялся суд, приговоривший его к 25 годам лишения свободы.

И снова Старр был примерным заключенным, и снова получил помилование, только на этот раз не от президента, а от губернатора. За проведенные в тюрьме пять лет он изучил законодательство страны и написал автобиографию.

Не успел Генри Старр выйти на свободу, как в Оклахоме (прежняя Индейская территория) одно за другим стали происходить дерзкие ограбления банков. С марта 1914 года по январь 1915 в этом штате лишились своих денег 14 банков! Все ограбления совершались в дневное время и без кровопролития. За помощь в поиске неизвестных бандитов было назначено крупное вознаграждение, но это не принесло результатов. Многие вспомнили тогда о знаменитом налетчике Генри Старре, а губернатор даже назначил награду за его голову. Старр всячески отрицал свою причастность. Он писал губернатору: «Похоже, меня будут обвинять всю оставшуюся жизнь, даже если я буду находиться в Австралии». И действительно, доказательств его причастности найти не могли… пока он не рискнул ограбить два банка одновременно. В 1892 году то же самое пыталась проделать банда Далтона в Коффейвилле. После этого она перестала существовать…

Семь всадников въехали в оклахомский городок Страуд утром 27 марта 1915 года. Один остался с лошадьми, остальные разделились на две группы по трое и двинулись по Главной улице. Они одновременно вошли в оба расположенных в городе банка — Страудский государственный и Первый национальный. Вышли они тоже одновременно, ведя перед собой одиннадцать заложников. Общая добыча составила 5815 долларов.

Но жители городка уже прознали об ограблении и не собирались выпускать бандитов. Завязалась перестрелка. Семнадцатилетний Пол Керри схватил в мясной лавке обрез и спрятался на аллее. Когда один из грабителей высунулся из-за «живого щита» заложников, Керри выстрелил. Пуля попала бандиту в бедро, раздробив кость. Раненым оказался сам Генри Старр.