WALKA O POWRÓT NA SZCZYT (sezon 2004/2005)

Do kolejnego sezonu Mostostal przystąpił z nowym szkoleniowcem, Waldemara Wspaniałego zastąpił Rastislav Chudik. W tym sezonie kędzierzynianie radzili sobie ze zmiennym szczęściem. Pokonując mistrza Polski (Jastrzębski Węgiel) zespół trenera Chudika rozpoczął udanie. Szybko jednak czarne chmury zebrały się nad Mostostalem, który przy serii porażek znalazł się na niechlubnym, przedostatnim miejscu w klasyfikacji. Pokazując charakter i walkę do końca Mostostal przełamał się po efektownym zwycięstwie z wicemistrzem kraju, urywając punkty również innym wyżej notowanym rywalom. Nerwowy start sezonu odbił się jednak na pozycji końcowej zespołu. Kędzierzynianom pozostała walka o piąte miejsce, a więc cel minimum wyznaczony przez zarząd na ten sezon. Finalnie udało się utrzymać tę pozycję, zespół czekały jednak zmiany.

NAJGORSZY SEZON W HISTORII (sezon 2005/2006)

Przebudowę rozpoczęto od zmiany szkoleniowca (Rastislav Chudik został zastąpiony przez Wojciecha Drzyzgę), z Kędzierzynem pożegnali się również Piotr Lipiński, Duszan Kubica, Jarosław Stancelewski, Artur Augustyn i Karol Szramek. Nowymi twarzami w szeregach utytułowanego klubu byli Damian Domonik, Petr Zapletal, Bartosz Kurek i Martin Sopko. Fani Mostostalu marzyli o powrocie swojego zespołu na szczyt, celem (na miarę możliwości) postawionym przed drużyną była walka o miejsce w czołowej czwórce. Zderzenie z ligową rzeczywistością było jednak wyjątkowo bolesne, po udanym starcie w pierwszej rundzie fazy zasadniczej, przyszedł kryzys. Cierpliwość prezesa Pietrzyka zakończyła się przy serii 10 porażek z rzędu i na etapie fazy play-off posadę stracił Wojciech Drzyzga, do końca sezonu Mostostal miał prowadzić dotychczasowy asystent szkoleniowca – Andrzej Kubacki Tego sezonu nie udało się jednak uratować, kędzierzynianie zajęli 8. miejsce, co było najgorszym wynikiem w historii klubu.

NADZIEJA WRACA (sezon 2006/2007)

Po niechlubnym sezonie 2005/2006 przyszłość klubu stanęła pod znakiem zapytania, upór prezesa Pietrzyka i wsparcie sponsorów pozwoliło Mostostalowi przystąpić do kolejnego sezonu. Prowadzenia drużyny podjął się trener Andrzej Kubacki, asystentem szkoleniowca został Roland Dembończyk. Wyciągając wnioski z poprzedniego sezonu tym razem nie było głośnych deklaracji mówiących o konkretnym miejscu w tabeli. Zespół miał prezentować dobrą siatkówkę, do drużyny dołączyło kilku nowych zawodników, najgłośniejszym transferem było jednak sprowadzenie do Kędzierzyna-Koźla Marcina Nowaka. Ze względu na sezon reprezentacyjny zmagania w kraju wystartowały nieco później, podopieczni trenera Kubackiego rozpoczęli od udanego występu w Pucharze Polski, nie zwojowali jednak tych rozgrywek. Kędzierzynianie nie grali źle, wciąż jednak brakowało wyników, swoją sytuację Mostostal uratował na finiszu fazy zasadniczej. W fazie play-off podopieczni trenera Kubackiego pokazali charakter i byli o włos od wygrania rywalizacji z jastrzębianami. Do sukcesu zabrakło niewiele, zamiast walki o medale pozostała jednak gra o 5. pozycję. Finalnie Mostostal ten sezon zakończył na 6. miejscu, pojawiło się jednak światełko w tunelu.

ZAKSA KĘDZIERZYN-KOŹLE (sezon 2007/2008)

Kolejny sezon przyniósł zmiany. Większościowym udziałowcem klubu zostały Zakłady Azotowe, nazwa klubu (Mostostal-Azoty Kędzierzyn – Koźle) pozostała niezmienna, jednak drużyna została zgłoszona do rozgrywek pod nazwą ZAKSA Kędzierzyn-Koźle. Istotnym wzmocnieniem było sprowadzenie do Kędzierzyna-Koźla Jakuba Novotnego, Czech odpłacił się dobra grą, będąc jednym z wyróżniających się zawodników. Do ZAKSY dołączył również reprezentant Polski – Łukasz Żygadło. ZAKSA miała mierzyć w miejsce premiowane grą w europejskich pucharach, o udanym początku na ostatniej prostej fazy zasadniczej niespodziewana porażka w Bydgoszczy skomplikowała sytuację ZAKSY. W play-off kędzierzynianie ponownie trafili na Jastrzębski Węgiel, ulegając rywalom. W walce o piąte miejsce ZAKSA walczyła z Resovią, niestety również tym razem góra byli rywale.

POWRÓT NA SZCZYT (sezon 2008/2009)

Chcąc wrócić do czołówki w ZAKSIE musiało dojść do przetasowań. Pierwszą zasadniczą zmianą było pojawienie się nowego szkoleniowca, prezes Pietrzyk po raz kolejny udowodnił, że nie obawia się podejmowania odważnych decyzji, powierzając zespół debiutującemu w tej roli Krzysztofowi Stelmachowi. Andrzej Kubacki pozostał jednak z drużyną, tym razem w roli asystenta szkoleniowca. Nie był to koniec zmian, skład kędzierzynian został bardzo mocno przebudowany, do ZAKSY wrócił Robert Szczerbaniuk, dołączyli m.in. Michał Masny, Michał Ruciak czy Dominik Witczak oraz zaciąg kanadyjski (Dan Lewis/ Terence Martin). Cierpliwość fanów ZAKSY została wynagrodzona, po udanym sezonie zasadniczym do fazy play-off podopieczni trenera Stelmacha przystąpili z drugiego miejsca. Po zwycięstwie z ekipą z Warszawy o finał kędzierzynianie walczyli z Resovią. Niestety mimo walki rywalizację wygrali siatkarze z Podkarpacia, a drużynie trenera Stelmacha pozostała walka o brąz. Również tym razem ZAKSA musiała uznać wyższość rywali, na najniższym stopniu podium stanęli jastrzębianie. ZAKSA po trudnych latach wróciła jednak do ligowej elity.