Оказавшись перед угрозой разорения, Ганза снарядила против витальеров две экспедиции. Обе они потерпели крах, хотя во второй, организованной в 1394 году, со стороны Ганзы участвовали тридцать пять хорошо оснащенных кораблей с тремя тысячами отборных рыцарей. Угроза стала теперь всеобщей, и в 1395 году Маргарита освободила Альбрехта, надеясь этим шагом хоть немного разрядить обстановку. Но обстановка не разряжалась. Каждый корабль, каждую эскадру все и везде принимали теперь за пиратские, не обращая никакого внимания на флаг.
Иногда это приводило к совершенно невероятным курьезам, будто списанным со страниц плохого приключенческого романа. Так, в 1396 году датский флот, высланный «королевой пиратов» Маргаритой из Кальмара в Висби против витальеров, по ошибке вступил в бой с ганзейскими кораблями, тоже свято уверенными, что нарвались на пиратов. Пока моряки обоих флотов добросовестно истребляли друг друга сперва на воде, а потом и на улицах города, витальеры были в каком-то очередном рейде. Возвратившись из него, они с изумлением узнали, что стали единственными властителями моря.
Но ганзейские города придерживались иного мнения, они не думали сдаваться. Почти непрерывно они высылали против пиратов одну экспедицию за другой, хотя редко какая из них оказывалась успешной. Наоборот, не в диковину были случаи, когда матросы кораблей-охотников прельщались вольной и сытной жизнью и пополняли собою ряды рыцарей морских дорог.
Хроники того времени свидетельствуют, что тюрьмы всех городов были переполнены пленными пиратами и что «палачи не справлялись со своей работой и брали себе помощников», но это не должно вводить в заблуждение: не следует забывать, какие это были города и какие в них были тюрьмы. Экипаж одного захваченного корабля (например капера Мольтке с сотней его молодцов, плененных штральзундцами) вполне мог заполнить собой до отказа несколько таких каталажек.
Может быть, именно этим обусловливались нередкие случаи расправы на месте, причем методами, заимствованными из арсенала самих же пиратов: «Жителям Штральзунда удалось захватить один из разбойничьих кораблей. После этого команду заставили также лезть в бочонки (в ответ на аналогичное действие пиратов). Потом был объявлен приговор, согласно которому, все, торчащее из бочек, должно быть срублено палачом».
Живучесть витальеров казалась сверхъестественной в те суеверные времена, и знатоки классической филологии все уверенней производили название братства от латинского «виталис» - жизненный, живой.
В июле 1397 года витальеры вдруг вспомнили о богатом городе Стокгольме, выстоявшем с их помощью против датчан. Времена переменились, теперь пираты думали только о добыче, ожидавшей их за стенами шведской столицы. Свейн Стуре, укомплектовав сорок два корабля тысячью двумястами головорезами, двинулся на штурм города. Он несомненно увенчался бы успехом, так как стокгольмский бургомистр Альберт Руссе уже обсуждал с членами городского магистрата условия сдачи. Но неожиданно витальеры получили известие о смерти своего господина и покровителя Эрика, и это удручающее обстоятельство посеяло брожение в головах пиратских вожаков, так как сводило на нет все их каперские свидетельства и превращало в обыкновенных пиратов без всякого прикрытия. Те из них, кто еще не окончательно порвал со своим аристократическим прошлым, заколебались и решили выйти из игры. Это спасло Стокгольм. Но это же и погубило витальеров, ослабленных раздорами.
Воспользовавшись тем, что Готланд остался без хозяина, Маргарита сочла момент как нельзя более удобным для захвата Висби. Не доверяя собственным полководческим талантам после трагикомедии 1396 года и не желая понапрасну рисковать, она призвала на помощь крестоносцев. В 1398 году войско рыцарей креста двинулось на Готланд, и это второе появление тевтонов в западной Балтике оказалось роковым для витальеров.
31 марта орденский флот, усиленный ганзейскими и датскими судами и насчитывавший восемь тысяч кораблей с пятью тысячами отборных воинов под командованием магистра Конрада фон Юнгингена бросил якоря южнее города Висби. Однако ни закованные в броню рыцари, ни осадные машины, ни предательство готландцев не помогли тевтонам. После длительной осады магистр вынужден был заключить со Стуре перемирие. По его условиям Готланд «на вечные времена» становился владением ордена, а Стуре и около двух тысяч уцелевших витальеров получали право отбыть на своих кораблях, куда пожелают. Свейн Стуре и некоторые вожаки из аристократов примирились с Маргаритой и стали добропорядочными горожанами, многие витальеры избрали местом своих набегов Ботнический и Финский заливы с устьем Невы. Большая же их часть ретировалась на остров Гельголанд и укрепилась там, нависнув дамокловым мечом над Бременом и Гамбургом.