Nurmijärvellä syntynyt Kolehmainen sai kiekko-oppinsa HIFK:ssä. Muutama ensimmäinen vuosi kilpasarjoissa sujui vaatimattomasti. Esimerkiksi kaudella 1996-97 HIFK ei selviytynyt edes C-nuorten SM-loppusarjaan. Tuolloisesta joukkueesta Kolehmaisen lisäksi liigaympyröihin nousivat sittemmin kuitenkin Toni Häppölä, Patrik Lostedt ja Tuukka Mäkelä.
Seuraavaksi kaudeksi Kolehmainen siirtyi ikäluokkaa ylemmäs. HIFK sijoittui B-nuorissa viidenneksi. Joukkueessa pelasivat myös Sami Ryhänen, Tony Salmelainen ja Matias Loppi sekä ”vierailevina tähtinä” Mikko Jokela jaNiklas Hagman. Vaikka Teemun 28 ottelun tehot (2+0) eivät kummoiset olleetkaan, sai hän kauden aikana maajoukkuedebyyttinsä. Hän pelasi Jukka Holtarin valmentamassa alle 17-vuotiaiden maajoukkueessa kolme ottelua.
Kolehmainen oli vakuuttanut taidoillaan myös A-nuoria valmentaneet Harri Rindellin ja Simo Saarisen ja nousi kaudeksi 1998-99 A-juniorien ryhmään. Kollien kausi sujui heikosti, sillä joukkue joutui karsimaan sarjapaikastaan, vaikka ringissä olikin kentällisen verran maajoukkuenuoria. B-ikäluokka sen sijaan pelasi mitaleista, ja niinpä Kolehmainenkin palasi kevääksi porukkaan.
HIFK voitti kauden päätteeksi B-nuorten pronssia kaadettuaan päätöskamppailussa Bluesin. Kolehmainen oli nimekkään joukkueen avainpelaajia. Joukkueessa oli todellakin potentiaalia vaikka muille jakaa: Kolehmaisen, Häppölän, Lostedtin, Mäkelän ja Salmelaisen lisäksi joukkueessa pelasivat muun muassa Tuomo Ruutu, Kim Hirschovits, Carlo Grünn, Joonas Vihko, Turo Järvinen, Ilkka Pikkarainen, Semir Ben-Amor, Antti Pihlgren, Antti-Pekka Lamberg ja Ville Viitaluoma!
Kolehmainen pelasi kaudella 1998-99 myös neljä ottelua alle 18-vuotiaiden maajoukkueessa. Seuraavalla kaudella hän otti vakiopaikan Pasi Kaukorannan ja Harri Rindellin komentoon siirtyneistä A-nuorista. Nippu oli jälleen kova, mutta sijoitus pettymys: 8. Aiempien joukkuekavereiden lisäksi pelipaikasta puolustuksessa kisailivat nyt myös Mikko Kurvinen, Antti Weckström ja Jani Honkanen. Kolehmainen pelasikin 30 otteluaan melko pienessä roolissa, eikä esiintynyt pudotuspeleissä.
Taistelua liigapaikasta
Kaudella 2000-01 A-nuorten ”dream team” viimein onnistui pelaamaan lähes materiaalinsa edellyttämällä tasolla. Kolehmainen oli railakkaasti hyökänneen joukkueen neljänneksi tehokkain puolustaja, heti Lambergin, Weckströmin ja Mikko Ilkan jälkeen. Runkosarjassa HIFK oli jyrännyt vastustajan toisensa jälkeen, eivätkä pudotuspelitkään hassummin alkaneet. Finaalisarjassa Tapparaa vastaan tapahtui kuitenkin totaalinen romahdus. Toisessa pelissä Tampereella pataan tuli törkein 9-0-lukemin ja ykkösveskari Tomi Nyman ”vain katosi” sen jälkeen. Tappara vei ottelusarjan ja SM-kullan voitoin 3-1.
Kolehmainen pääsi samana keväänä kehiin myös aikuisten SM-liigassa: neljässä runkosarja- ja yhdessä playoff-ottelussa. Debyytissä (6.3.2001) vastassa oli Pelicans ja Kolehmaisen paikka junnuhenkisessä kolmoskentässä, yhdessä Lambergin, Grünnin, Viitaluoman ja Pikkaraisen kanssa. Päätöskamppailussa viisikko oli ylennetty jo ykkösnyrkiksi.
HIFK nosti vuosituhannen murrosvaiheessa runsaasti omia nuoriaan edustusmiehistöön, joten Kolehmaisenkin haaveena oli saada seuraavalla kaudella lisää liigakokemusta. Tulihan sitä, muttei paljoa. Samoista jämäminuuteista kisailivat Honkanen, Lamberg ja Ilkkakin. Kolehmainen sai liigassa kauden aikana tililleen 13 ottelua, joista osassa pelasi laitahyökkääjänäkin. Ainoiksi tilastomerkinnöiksi jäi kaksi miinusmaalia. Junioreista hän haki peliaikaa muutaman ottelun verran, Mestiksen Haukoista kaikkiaan 19 ottelun verran.
Järvenpäässä peliaikaa ja tehojakin tuli mukavasti, joten sinne vei Kolehmaisen tie myös seuraavana syksynä liigasopimuksesta huolimatta. Lopulta Kolehmainen ehti edustaa kauden 2002-2003 aikana peräti kolmea eri Mestis-seuraa. Järvenpäästä Kolehmainen siirtyi lokakuun lopussa Mikkeliin, kun Mestiksen kärkiseura Jukurit tarvitsi lisämiehiä otteluruuhkansa keskellä. Puolustaja saikin maistella kansainvälisten otteluiden tunnelmaa Jukureiden matkassa Continental Cupissa.
Mikkelistä Kolehmainen palasi HIFK:iin – mutta vain pieneksi hetkeksi. Hän pelasi tammikuun lopussa tappiollisessa ottelussa Lukkoa vastaan laitahyökkääjänä, ja sai valmentaja Alpo Suhosen avautumaan julkisesti:
– Lahjoitettiin kolme maalia. Voin kertoa ne lahjoittajatkin ettei jää mitään epäselväksi. Teemu Kolehmainen, Robert Kantor ja Niklas Hedberg olivat Lukon voiton takuumiehet, paineiden alla ollut valmentaja latasi tökerösti.
Kymppipaita sai läksytyksen myötä jäädä rauhassa odottamaan Jere Karalahden paluuta HIFK:iin. Siirtorajan viime hetkillä loukkaantumisista kärsinyt Kiekko-Vantaa hankkikin Kolehmaisen riveihinsä. Kauppaan sisältyivät ilmeisesti myös uudet kädet, sillä Kolehmainen pelasi siihenastisen uransa parhaan kevään. Junioreissakaan harvemmin pistetehtailuun äitynyt puolustaja tuplasi runkosarjan 10 viimeisessä matsissa kauden pistesaldonsa ja oli pudotuspeleissä kerrassaan liekeissä.
Kiekko-Vantaa eteni sarjassa aina loppuotteluihin saakka. Thomas Heinrichsin parina ykköskentässä pelannut Kolehmainen ehti takoa yhdeksässä pudotuspelissään tehot 3+4 ja jäi viisi maalia plussalle, ennen kuin loukkaantui toisessa finaalipelissä. Jukurit nousi lopulta mestaruuteen 2-0-tappiotilanteesta.
Rikkonaisia kausia Mestiksessä
Vahva kevät poiki Kolehmaiselle tarjouksia ja kesän 2003 mies hikoilikin Lahdessa näyttöjä antaen. Tryout-miehistä pelipaikka meni kuitenkin Sportin Jussi Heikkiselle. Kolehmainen ja Toni Mustonen saivatkin alkaa etsiä uutta osoitetta vain muutamaa viikkoa ennen sarjan alkua. HIFK:ssä mies käväisi pelaamassa harjoituspelejä vanhaa seuraansa pakkipulassa avittaen, mutta sopimusta ei sen kummemmin harkittukaan, vaikka Suhonen monoa olikin jo edelliskaudella saanut.
Vantaalla Kolehmainen otettiin kuitenkin ilolla vastaan – ja toinenkin kokonainen Mestis-kausi sujui mallikkaasti, vaikka pakkipari vaihtuikin vierellä alinomaa. Hän pelasi niin Lostedtin, Antti Nyrhisen, Juha Kaunismäen kuin Tuomas Luotosenkin kanssa.
Kausi päättyi kuitenkin yhtä ikävästi kuin vuotta aiemminkin, tällä kertaa tosin jo pudotuspelien ensimmäisellä kierroksella. Kolehmainen syötti neljännessä pelissä tasoitusmaalin, kun pelikellossa komeili jo aika 59.43. Jukurit venyi kuitenkin pakkovoittoon jatkoajalla – ja siinä välissä Kolehmainenkin oli ehtinyt loukkaantua, ja joutui seuraamaan tappioon päättyneen ratkaisukamppailun kaukalon laidalta.
Kausi 2004-2005 puolestaan meni Kolehmaiselta täysin pipariksi. Se käynnistyikin erikoisesti: Allsvenskan-seura Bodens IK ehti kesäkuun lopussa uutisoimaan Kolehmaisen siirtyvän länsinaapuriin, mutta vain pari viikkoa myöhemmin K-Vantaa kertoi tehneensä jatkosopimuksen avainpelaajansa kanssa.
Pelit Mestiksessä päättyivät kuitenkin loukkaantumiseen jo varhaisessa vaiheessa. Kolehmainen ehti pelata kauden alussa vain muutaman ottelun ennen kuin loukkasi polvensa. Joulukuussa hän yritti paluuta jäälle, mutta polvi vääntyi uudestaan. Muutamaa kuukautta myöhemmin Kolehmainen pääsi taas jäälle – ja heti ensimmäisessä ottelussa napsahti sormi poikki. Siitä puolustaja ei enää ehtinyt toipua, joten kauden viralliset pelit jäivät yhdeksään.
Mies kelpasi kuitenkin yhdessä seuratoverinsa Miikka Lindholmin sekä Janne Jokilan kanssa Pelicansin testiin seuraavallakin kaudella. Paikka lahtelaispuolustuksessa meni kuitenkin jo ennen harjoituspelien alkua Jarkko Gladille ja edessä oli uuden seuran etsintä. Tällä kertaa se ei kestänyt kauaa, sillä vain muutamaa päivää myöhemmin Kolehmainen oli ruotsalaisen Borås HC:n miehiä.
Tällä kertaa Kolehmainen jopa pelasi Ruotsissa. Aika länsinaapurin ykkösdivisioonassa jäi kuitenkin lyhyeksi, sillä Kiekko-Vantaan ajoilta tuttu valmentaja Jami Kauppi hankki vanhan luottopakkinsa tultuaan marraskuussa Haukkojen päävalmentajaksi. Järvenpäässä Kolehmainen ehti pelata 18 ottelua kerrassaan erinomaisin tilastoin. Pisteitä otteluissa kertyi 7+4, ja vielä kovempi oli tehotilaston nollalukema – Haukat kun kynti jo syksyllä varsin synkissä vesissä.
Järvenpääläisen Mestis-kiekkoilun lopun alku nähtiin siirtorajan lähestyessä, kun pelaaja toisensa perään jätti uppoavan laidan. Kolehmainen ja toinen Haukkojen tehopuolustaja Kai Öhberg pakkasivat kimpsunsa ja kampsunsa ja hyppäsivät Kajaanin junaan muodostaakseen Hokille ykköspakkiparin.
– Meillä oli tarve puolustajista ja pojilla oli kova halu tulla pelaamaan tänne. Se on iloinen asia, sillä heidän tulonsa myötä puolustajapuolelle saadaan kaivattua laajuutta ja kiertoa aikaiseksi, Hokin manageri Olli-Pekka Hakkarainen kommentoi.
Kolehmainen aloitti Hokki-uransa heti vakuuttavasti, vaikka mies itse vaatimattomana olikin.
– Tänään kulki. Ehkä tässä rupeaa pääsemään peli peliltä paremmin sisään Hokki-paitaan. Onhan se alku aina vaikeaa kun on pelannut puolet runkosarjasta tuttujen jätkien kanssa ja sen jälkeen mennään uuteen koppiin ja lyödään täysin uusi systeemi eteen. Kolmesta neljään peliä siinä meni ennen kuin päästiin kunnolla sisään, mutta hyvin ollaan viihdytty täällä Öhbergin Kaijun kanssa, puolustaja mietiskeli Jatkoajalle 21.2. pohjustettuaan viidennessä ottelussaan voiton Hermeksestä maalein 2-1.
Kevään aikana Kolehmainen nousi jopa kajaanilaissankariksi. Mies esiintyi vahvasti jo pudotuspelien ensimmäisellä kierroksella, vaikka kertaalleen KooKoon Timo Nurmbergia rusikoituaan suihkuun joutuikin. Välieräsarjassa hän oli joukkueensa paras pelaaja, laukoen jukuriverkkoon voittomaalin sekä kolmannessa että neljännessä välierässä. Pisteet 2+2 ja tehotilastolukema +4 ei kuitenkaan yksin riittänyt, vaan kausi päättyi tappioon pronssipelissä. Se oli kuitenkin kainuulaisten paras playoff-kevät ikinä – ja Kolehmainen nousi seuran kaikkien aikojen tehokkaimmaksi puolustajaksi pudotuspeleissä kertaheitolla.
Keikkamies ei kuitenkaan jäänyt nälkämaahan, vaan siirtyi valmentaja Vladimir Kolekin perässä Kouvolaan. Vaikka mies ei ollut pahemmin pääkaupunkiseudun ulkopuolella kiekkoillutkaan, löytyi KooKoosta muitakin tuttuja. Samaan aikaan uutisoidut muut uudet pelaajat, Miikka Lindholm ja Antti Nyrhinen, olivat tuttuja Vantaalta vuosilta 2003-05. Lindholmin kanssa Kolehmainen oli pelannut myös edellissyksynä Haukoissa. Hyökkääjistä tuttuja olivat myös Ville Vimpari Hokista sekä Tuomas Ilola ajoilta HIFK:n A-nuorissa.
