Утратив надежду на успех, князь Юрий Галицкий в 1428 г. признал Василия I «братом старейшим» и отказался от претензий на великокняжеский престол. Но смирить себя перед малолетним племянником он все же не мог. По условиям договора («докончания») 1428 г., Юрий выговорил себе право не участвовать в походе, если Василий II брал на себя общее командование полками. В этом случае он ограничивался посылкой в поход сыновей.
Князья издавна пользовались правом призывать к себе «вольных слуг», которые при этом сохраняли свои вотчины. «Докончание» ограничило эту важнейшую привилегию князя, усиливавшую его дружину. Юрий обязался «князей служебных» (из великого княжества) «с вотчиною собе в службу не приимати».
В эпоху средневековья достоинства князя измерялись прежде всего его воинской доблестью, подвигами в защите отечества. Потомки Донского не унаследовали от отца его воинского таланта и славы. Московское княжество вступило в полосу кризиса и военных неудач. Оставаясь татарским улусом, Русь оказалась втянутой в орбиту литовского влияния.
Осенью 1430 г. московский, тверской и рязанский князья были вызваны в Вильну. Витовт готовился одеть на себя королевскую корону. Однако коронация не состоялась, а вскоре после отъезда гостей Витовт умер. Год спустя в Москве скончался митрополит Фотий. В Литве к власти пришел свояк князя Юрия Свидригайло. Василий II не мог более противопоставить врагам союз с Литвой.
После смерти Витовта, повествует летопись, Юрий «разверже» союз с Василием II и отослал в Москву текст договора 1428 г. В подлиннике была тогда же сделана помета: «А сю грамоту князю великому прислал (со) складною (грамотой. — Р. С.) вместе князь Юрьи, к орде ида». Складную грамоту посылали при объявлении войны. Но не это вызвало переполох в Москве. Бояре были смущены тем, что удельный князь в соответствии с первым докончанием 1425 г., решил отправиться в Орду, чтобы судиться с племянником из-за ярлыка на великое княжество. Исход суда зависел от того, кто первый прибудет к ханскому двору и успеет доказать свою преданность Орде. В таких условиях правитель Всеволожский убедил Василия II ехать в Орду и лично возглавил его свиту. К этому времени государю исполнилось пятнадцать лет и он достиг совершеннолетия.
Отчет о переговорах в Орде был составлен московской канцелярией при участии правителя И. Д. Всеволожского. Отчет почти целиком состоял из пересказа речей Всеволожского, похвал по поводу его удивительных дипломатических успехов. Однако при ближайшем рассмотрении эти успехи выглядели, как полнейшее поражение.
Отправившись в Орду для решения спора о владимирском престоле, русские князья поставили себя в унизительное и трудное положение. Улу-Мухаммед проявил пренебрежение к князьям из руссого улуса, продержав их у себя почти год. Василий II был поселен в юрт к московскому даруге (сборщику дани с Московского государства) Минбулату. Князя Юрия забрал на зиму в Крым мурза Тегин. Летом 1432 г. князья были приглашены в ставку. Василий II попросил себе ярлык на великое княжение, но Юрий опроверг его доводы «летописцы старыми списки и духовную отца своего великого князя Дмитрия». В духовной значилось, что по смерти Василия II стол переходит по старшинству брату, т.е. Юрию. В диспут вмешался Всеволожский. Он заявил, что Юрий желает получить княжение «по мертвой грамоте отца своего, а не по твоему жалованию волного царя». Летописец старался преподнести эти слова, как триумф московской дипломатии. Но в действительности речь правителя свидетельствовала о полной капитуляции.
Правитель постарался убедить властителя Орды, что его московский государь ищет княжества из ханской руки — «твоего улуса, по твоему цареву жалованию и твоим девтерем и ярлыком». Согласно московской версии демарш Всеволожского привел к немедленному успеху. Летописи независимого происхождения свидетельствуют об обратном. Миссия правителя закончилась провалом. Орда по традиции делала ставку на сильнейшего из русских князей. Но Улу-Мухаммед не был уверен, что малолетний племянник одолеет дядю. По Новгородской летописи «выидоша князи рустин из Орды без великаго княжения». О том же говорит и псковский летописец: Василий II с дядей и все бояре с ними выехали из Орды «добры и здравы, а княжений не взят ни един». Лишившись на год государя, московский правящий круг должен был признать, что решение о поездке в Орду явилось серьезной ошибкой. Итоги миссии Всеволожского вызвали глубокое разочарование. Орда направила на Русь вслед за князьями посла Мансыр-Улана. Он посадил Василия II на владимирский престол, но одновременно стал добиваться от него выполнения финансовых обязательств.
Правитель Всеволожский навлек на свою голову общее негодование, и ему пришлось прибегнуть к помощи книжников, чтобы восстановить добрую славу семьи.
После смерти зятя князя Андрея Радонежского Всеволожский стал опекуном его великого княжества. По-видимому, не позднее 1432 г. книжники Троице-Сергиева монастыря, располагавшегося в уделе, составили «Сказание о Мамаевом побоище». Сказание прославляло как князя Андрея Владимировича, так и отца правителя. Дмитрий Донской якобы вверил передовой полк «князьям» Дмитрию и Владимиру Всеволожским. «Князья» храбро атаковали татар в самом начале битвы. Дмитрий, отец Ивана Всеволожского никогда не носил княжеского титула. Что касается сведений о его выдающейся роли в битве, они не подтверждаются другими источниками. Сказание имело широкий круг читателей, и призвано было доказать, что сын «князя» — героя Мамаева побоища не может быть «предателем» христианства и пособником Орды.
По обыкновению летописи давали подробные сведения о размерах экстренных сборов в пользу «царя», их взыскания с населения и пр. Правитель позаботился о том, чтобы сведения такого рода вовсе не попали в отчет о его посольстве. Василий II, заявил боярин хану, не один год сидит на своем престоле, «а на твоем жалованье, тебе, своему государю, волному царю правяся». Этими словами исчерпывались все указания на «службу» Москвы Орде, даннические отношения и пр. Между тем вопрос о дани занимал центральное место в переговорах. Хан недаром поместил Василия II в дом московского даруги — сборщика дани. О размерах дани свидетельствовали слова князя Юрия, включенные в княжеский договор 1433 г. Великий князь, признавался удельный князь, «платил в Орде за мою отчину за Звенигород и за Галич два выхода и с распанами». Как видно, татары получили двойную дань с надбавками как с удела, так и с великого княжества. Орда требовала наличных денег, и Всеволожскому пришлось занять деньги под огромные проценты.
Улу-Мухаммед не желал жертвовать князем Юрием, так как московские распри позволили ему без каких бы то ни было усилий и пролития крови возродить свою власть над Русью. Ордынский посол привез ярлык не одному Василию II, но и Юрию, получившему выморочное княжество Дмитровское, удел брата Петра. Но Василий II не посчитался с волей хана, изгнал наместника Юрия из Дмитрова и присоединил город к своей московской вотчине.
Миссия в Орду фактически положила конец карьере И. Д. Всеволожского, как правителя. Он стал слишком непопулярной фигурой в столице и при дворе. Имеются сведения, что правитель намеревался сосватать свою дочь Василию II. Но брак в великокняжеской семье стал предметом соперничества в придворных кругах. Василию II сосватали его родственницу — внучку Владимира Андреевича Храброго. Заключению брака способствовали бояре Кошкины. Невеста великого князя была родной племянницей боярина И. Ф. Кошкина, известного противника Орды.
Борьба за власть внесла раскол в московскую думу, что имело самые серьезные последствия. Стремясь сохранить пост правителя, Всеволожский пытался найти опору в уделе князя Юрия. Задумав породниться с семьей удельного князя, он объявил о помолвке своей дочери со старшим сыном Юрия Василием Косым. Затея правителя было рискованным шагом. Князь Юрий готовился к войне с племянником из-за Дмитрова. Противники Всеволожского в думе использовали этот промах, чтобы покончить с его влиянием при дворе. Юрий не попал на свадьбу Василия II. Но его сыновья пировали за свадебным столом. Свадебное пиршество было омрачено родственной ссорой. Сын казначея И.Ф. Кошкина (по другой версии П.К. Добрынский) донес вдовствующей матери Софье, что Василий Косой явился на свадьбу в золотом поясе, «на чепех с камением». Пояс якобы был украден из великокняжеской казны, перешел в руки И.Д. Всеволожского, а от него с приданным Косому. Донос Кошкина заключал в себе много неувязок, но властная Софья не постеснялась бросить оскорбление в лицо гостю, после чего сорвала пояс со свояка. Василий с братом Дмитрием Шемякой, «раззлобившися», покинули Москву и укрылись в княжестве отца в Галиче. И. Д. Всеволожский, запятнанный подозрением, не захотел оставаться на службе у великого князя. Предполагали ли бывший правитель начать борьбу с государем, неизвестно. Во всяком случае, он уехал из столицы не в Галич, а в удел Константина, лояльного по отношению к Василию II. Существенное значение имело еще одно обстоятельство. В случае отъезда к Юрию бывший правитель, в соответствие с докончанием, разом бы лишился своих обширных вотчин.
