Gdy zaczął wymyślać kolejne piosenki, okazało się, że jednak potrzebuje muzyków. Zaprosił sekcję rytmiczną Kultu - basistę Irka Wereńskiego i perkusistę Andrzeja „Szczotę” Szymańczaka oraz gitarzystę Sławka Pietrzaka, kiedyś muzyka Kultu, a potem właściciela SP Records, firmy wydającej płyty Kazika i Kultu. W nagraniu uczestniczyli również skreczer DJ Feel-X, gitarzysta Adam Burzyński oraz klarnecista i saksofonista Jerzy Mazzoll. 12 groszy to płyta bez słabych punktów, gdzie Kazik niemal po mistrzowsku połączył „żywą” muzykę ze sztuką samplingu. Przebojami okazały się też utwory Maciek, ja tylko żartowałem, Sztos, który powstał do filmu Olafa Lubaszenki o tym samym tytule i Idę tam, gdzie idę. Częścią promocji Sztosu były trzy koncerty, podczas których grano piosenki z 12 groszy.
Niemal równocześnie ukazała się najbardziej eksperymentalna płyta z udziałem Kazika - Rozmowy s catem podpisana przez Kazik Mazzoll i Arhythmic Perfection. To wynik sesji, jakie Kazik odbył w toruńskim studiu Mózg wraz z czołowymi przedstawicielami jassu. Płyta urzeka lekkością i swobodą, z jaką muzycy poruszali się po różnych płaszczyznach dźwiękowego świata. Czasami muzycy przedstawili zwarte piosenki, ale przeważnie zaskakiwali rozbudowanymi i nieokiełznanymi kompozycjami.
Trzy lata po 12 groszach Kazik przedstawił Melassę, która okazała się kontynuacją tamtej płyty. Tym razem głównym współpracownikiem Kazika stał się Olaf Deriglasoff, dawny lider zespołu Dzieci Kapitana Klossa, a później muzyk m.in. Apteki, Pudelsów, Homo Twist. Ważną postacią był też Piotr Wieteska, kiedyś współzałożyciel Kultu, a od 1995 roku jego menedżer. Największym przebojem okazała się piosenka Cztery pokoje, której współkompozytorem był właśnie Wieteska. W Czterech pokojach gościnnie zaśpiewała Edyta Bartosiewicz. Co ciekawe w nagraniach uczestniczył też inny dawny muzyk Kultu Jacek Szymoniak. Melassa przyniosła jeszcze dwa wielkie przeboje - balladę Gdybym wiedział to, co wiem z pięknym solem na fortepianie zagranym przez Leszka Możdżera (słynnego pianistę słychać jeszcze z Każdy potrzebuje przyjaciela i Do You Remember) i Mars napada z teledyskiem, w którym udział wzięli m.in. Maciej Maleńczuk, Muniek Staszczyk czy rodzina Kazika.
Kolejne dwie płyty zostały przez Kazika przygotowane we współpracy z Romanem Kołakowskim, wówczas dyrektorem Przeglądu Piosenki Aktorskiej we Wrocławiu. Już w 1999 roku Kołakowski zaproponował Staszewskiemu przygotowanie recitalu z piosenkami Kurta Weilla. Ów koncert miał miejsce w 2000. Później Kazik nagrał je na płytę Melodie Kurta Weill'a i coś ponadto, a oprócz songów słynnego kompozytora na płycie znalazło się miejsce na przeróbkę piosenki Nicka Cave'a Krzesło łaski. Największym powodzeniem cieszyły się Singapur i Ballada o kobiecie żołnierza.
Drugim przedsięwzięciem okazały się piosenki Toma Waitsa przetłumaczone przez Kołakowskiego. Kazik z zespołem wystąpili podczas Przeglądu Piosenki Aktorskiej w 2003 roku. Te same utwory nagrali potem na płytę Piosenki Toma Waitsa. Bourbon mnie wypełnia stał się przebojem, a cała płyta sukcesem artystycznym. Muzycy jeszcze tylko dwukrotnie zaprezentowali się w tym repertuarze, w warszawskiej Sali Kongresowej w maju 2003 i pół roku później w studiu radiowej Trójki. W nagraniu obu płyt pomogli mu muzycy na co dzień związani z Kultem (waltornista Krzysztof „Banan” Banasik, perkusista Tomek Ghoes, keyboardzista Janusz Grudziński, grający na trąbce Janusz Zdunek, gitarzysta Piotr Morawiec, saksofonista Tomasz Glazik) i KNŻ (gitarzysta Adam Burzyński, basista Michał Kwiatkowski) oraz Olaf Deriglasoff (gitary), Wojciech Jabłoński (gitary, perkusja), Andrzej Izdebski (gitara), a także obaj synowie Kazika - Kazio i Jan.
