Vuosituhannen vaihteessa, vuonna 1999 julkaistiin Puhkujen viides levy, lastenmusiikkia sisältävä vol. 2+2=5. Orkesteri kiersi ahkerasti Suomea, piti lastenkonsertteja lähiseudulla ja vähän kauempanakin, mm. Linnanmäellä ja teki yhteistyötä puolustusvoimien soittokuntien kanssa niin Tikkakoskella, Pohjois-Karjalassa kuin Kajaanissakin. Oli Lapinlahden Juusto- ja viinijuhlia, Harjavallassa kävimme pariin otteeseen Vasket vallassa -tapahtumassa ja vierailimme Joensuussa paikallisen opiskelijapuhallinorkesterin vieraana. Lisäksi vuonna 2000 orkesteri teki myös ekskursion Puolaan. Lieksan vaskiviikkojen ohella Hamina-Tattoossa tuli vierailtua useampana vuonna. Ylipäätään Puhkut kiersivät Suomea niin, että voidaan sanoa, ettei ole laaksoa, ei kukkulaa, ei sellaista niemennotkoa, jossa Puhkujen soitto ei olisi raikunut: Kainuun vaaroilta Pohjanmaan lakeuksille ja pääkaupungista Pohjois-Karjalaan.
2000-luvulle tultaessa Puhkupillejä luotsasivat Nikke Isomöttönen, Janne Ikonen, Tiiu Tuominen ja Marja Ikonen. Tuominen lienee puhkujen pitkäaikaisin kapellimestari; hän viihtyi 12 vuotta tahtipuikon ja yleisön välissä. Orkesterille oli vakiintunut useita lukuvuotta rytmittäviä esiintymisiä kuten Oluen ottajaiset yläkaupungin ravintoloissa Sohwissa ja Ylä-Ruthissa. Myös taiteellinen kevätkonsertti, entisen Jazzbarin nykyisen Popparin bilekeikat kevättalvella ja JYYn vappukeikat olivat varsin varmoina etappeina kalentereissa. Orkesteri täytti 20 vuotta vuonna 2003, jolloin pidettiin suuri juhlakonsertti Jyväskylän yliopiston Muisca-rakennuksen salissa. Vuonna 2002 orkesteri kävi äänittämässä Mikkelissä asti kuudennen levyn, joka sai nimen ”Symposium”.
Vuonna 2003 kapellimestarin paikalle astui Marjo Riihimäki. Hänen perässään tulivat puhallinmusiikkipuolella erikoistapaus, nimittäin alttoviulua pääaineenaan opiskellut, sittemmin sivusoitinorkesterissa käyrätorvensoittajana kunnostautunut Leena Toivanen sekä Olli-Pekka “Alfauros” Hiltunen. Leenan ja O-P:n esiinmarssiin liittyi myös Konnevedeltä lähtenyt juomakulttuurinen muutos: boolin syrjäytyminen ja Puhkuviinin keksiminen. Varusmiessoittokunnan ‘03 hyypiöt ja sittemmin kommuunikämppikset Ville Huovinen ja Jaakko Koivula taikoivat ensimmäisen viinierän, joka oli menestys huolimatta käymisohjeiden epäortodoksisesta seuraamisesta. Sittemmin viinivastuu siirtyi kolmannelle saman joukkion kekkeruusille, Nasulle ja edelleen kapellimestarina myöhemmin kunniaa niittäneelle Touko Raatikaiselle, jonka vaikutuksesta viineihin saatiin myös hyvää makua. Viiniperinne on jatkunut vahvana ja 2010-luvulta alkaen vetovastuu viinin laittamisesta on ollut Viinin jumalattarella, joka on löytynyt tyypillisesti trumpettisektiosta. Myös booli teki paluun Konnevedelle 2020-luvulla, kun viinin rinnalle tuli tarjolle alkoholiton Puhkubooli.
Leenan ja OP:n tuore visio ja yli-inhimillinen panostus siivitti Puhkut kiertueelle Viroon keväällä 2006 ja seuraavana vuonna edelleen Puhallinorkestereiden SM-kisoihin Tampereelle 2007, ja A-sarjasta pokattiin viides sija (pääasia oli, että paikallinen kilpakosija JPO piestiin). Näiltä ajoilta on myös peräisin sanapari “Hellyyden ehdoilla”, joka kuvaa silloisia (ja epäilemättä myös menneitä ja tulevia) läheisyydentäyteisiä keikkoja ja illanviettoja osuvasti.
Uudet tuulet koettelivat puhkumuotiakin: keltaisista, telttoja muistuttavista kauluspaidoista luovuttiin ja T-paidasta tuli puhkuasun kulmakivi. Uusia paitoja hankittaessa puhkulogolle piirrettiin kilpailijoita, mutta Jukka Viitasaaren klassinen näkemys evoluutiosta kyykytti äänestyksessä keltanokkaiset vastustajansa. Kokoja päätettäessä ainakin miesten S-koon sovituspaita oli venynyt hurjan kokoiseksi, minkä johdosta puhku-urokset tilasivat joukolla S:n paitoja. Paitojen saapuessa karu totuus ja navat paljastuivat, mutta ulkonäön muutos tuki rakkaudentäyteistä tematiikkaa. Keltamusta muoti sai pauloihinsa Leenan, joka teetätti ansioituneimmille puhkujille lahjoitettavia puhkulogollisia alusvaatteita. Leenan ja O-P:n vispaamisen tahdissa edettiin 25-vuotiskonserttiin asti.
Vuonna 2008 kapellimestarin suuriin saappaisiin astuivat Mikko Sateila ja Touko Raatikainen. 25-vuotiskonsertin jälkeen oli hyvä kerätä voimia tulevaan ja seuraavat pari vuotta soitettiin paljon jo olemassa olevaa ohjelmistoa ja tehtiin perinteisiä keikkoja. Näiden lisäksi puhkut ajautuivat toistuvasti perin eriskummallisiin tilaisuuksiin esiintymään, joista esimerkiksi käyköön Suolahden uusivuosi ‘08 ja yhden mummon laajuinen kuulijakunta. Mikon lähdettyä opiskelemaan Sibelius-akatemiaan Tanjaana Jaakkola tuli toiseksi kapellimestariksi.
Syksyllä 2009 Puhallus rantautui Jyväskylään ja päävastuu siitä lankesi tyypille, jonka tietoihin nojauduttiin vuosia puheenjohtajakautensa jälkeenkin: Lauri Nykäselle. Epäinhimillinen työtaakka saatiin hoidettua Laurimaisella tyyneydellä (”Nikolainkulman mainosstandi hajos eli sieltä tullee lasku. Teekkaritorvi kaatui sen päälle, mutta toisaalta me peruutimme pakettiautolla yhden heidän soitinkotelonsa päälle eli en olisi lähettämässä heille laskua, jos ei heiltäkään semmoista tule.”).