Троицу король также праздновал в Саксонии, для чего выбрали старинный епископский городок Хальберштадт. Только после празднования король возвратился назад в Баварию для подавления восстания, поднятого маркграфом Генрихом Швайнфуртским вместе со своим братом Эрнстом Бамбергским и Бруно, братом короля Генриха II. Все трое оказались связаны с Болеславом Храбрым. Генрих Швайнфуртский поддерживал кандидатуру Генриха II в надежде получить назначение на герцогство в Баварии. Однако король сослался на право баварцев самим делать выбор, имея совсем иные намерения относительно герцогства, остававшегося еще на тот момент его вотчиной.
Когда в 1003 году внезапно умер князь Владивой, Болеслав Рыжий под защитой Болеслава Храброго вернулся в Чехию. Однако поведение Болеслава Храброго оставалось совершенно непредсказуемым: он неожиданно взял в плен им же самим возвращенного на правление в Чехию Болеслава Рыжего. Мало того, он приказал выколоть Рыжему глаза и держал его под стражей до самой смерти. Таким образом, территория под патронатом Болеслава Храброго простиралась теперь от Балтийского моря до венгерских границ. Чувствуя себя независимым и сильным, он посмел запретить королю Генриху II покровительствовать над Чехией. Король, вынужденный бороться с приспешниками Болеслава во Франконии, чтобы вновь вернуть эту землю короне, не выдвигал войска против Болеслава Храброго. Летом 1003 года поляк опустошил восточные пограничные области империи и предпринял попытку двинуться через Эльбу на запад.
Генрих II не смог противостоять неожиданному ходу Болеслава Храброго, и, таким образом, выпад поляка поначалу оказался неотомщенным. Контрудар в феврале 1004 года также не принес успеха. Испытывая трудности на восточных рубежах, король решился на меры, вызвавшие многочисленное недовольство во многих городах страны. Он объединился в борьбе против Болеслава Храброго с язычниками славянами и лютичами, которые еще в 983 году и много раз после повергали пограничные области страны в хаос своими восстаниями. Король Генрих II рассчитывал благодаря данному военному союзу склонить оба племени к дружбе и в конце концов включить их в состав империи, дав им возможность интегрироваться, однако большинство поляков и саксонцев не поняли короля.
После победоносного завершения борьбы с Генрихом Швайнфуртским король позволил себе немного расслабиться и поохотиться в горах Шпессарта. 21 октября 1003 года он впервые встретился в монастыре Святого Бильда в Эльзасе с известным аббатом Одило из Клюни, считавшимся другом императрицы Адельгейды, и затем через Франконию возвратился назад в Саксонию, где в старинной резиденции Пельде по традиционному сценарию, сложившемуся еще при его предшественниках, отпраздновал Рождество.
Из Пельде король Генрих II направился через Дорнбург в Тебру у Аполды на Ильме, где располагалась резиденция архиепископа Гизелера Магдебургского. Король нашел Гизелера лежащим больным в постели. Королю удалось переговорить с епископом о возрождении аббатства Мерзебург, и Гизелер попросил время подумать об этом. Однако, не успев согласовать окончательно решение, 25 января 1004 года архиепископ умер. Смерть архиепископа Гизелера Магдебургского унесла одного из крупнейших и влиятельнейших представителей церкви империи. Вопреки протестам духовенства король Генрих II назвал преемником умершего священника своего друга и советника по вопросам управления Тагино. Еще Генрих Сварливый, очевидно, в благодарность за заслуги Тагино и для укрепления монашества, хотел назначить того преемником епископа Вольфганга в Регенсбурге в 994 году. Однако тогда король Оттон III и императрица Адельгейда решили по-другому, сделав преемником Гебхарда, так как никто из них не хотел видеть соратника Сварливого на столь ответственном посту.
После смерти Гизелера стало возможным возрождение епископства Мерзебург, ведь, по сути дела, Гизелер принял управление архиепископством Магдебург только при условии ликвидации епископства Мерзебург, руководимого им перед этим. Епископ по средневековым понятиям не имел права менять место правления.
2 февраля 1004 года архиепископ Виллигис рукоположил Тагино на пост архиепископа Магдебурга. Четырьмя днями позднее, приурочив планируемое событие к созыву 6 февраля 1004 года рейхстага, король Генрих II вновь основывает епископство Мерзебург, назначив капеллана Вигберта из придворной канцелярии епископом и повелев Тагино совершить рукоположение Вигберта.
Одно из происшествий, случившихся зимой, король не смог предотвратить из-за плохой погоды. Мятежники в Баварии все-таки не отказались от своих намерений. Вернувшись в Мерзебург, Генрих узнал – его брат Бруно удалился к их общей сестре Гизеле в Венгрию. Маркграф Генрих Швайнфуртский имел мужество покаяться и покориться королю, но тот не дал себя разжалобить и поместил арестованного мятежника в крепость Гибихенштейн. Вслед за тем двор переехал в Баварию.