A montenegrói labdarúgást az egykori Jugoszláviában elsősorban a Buducnoszt Podgorica (korábban Titográd) képviselte, de azért a tagállam más klubjai is megfordultak az élvonalban. A Sutjeska Niksic például a nyolcvanas évek közepén élte fénykorát, éppen akkor, amikor a városban született Vucinic elkezdett ismerkedni a sportággal - nem csoda, hogy a kis Mirkót a Sutjeskába vitték le a szülei futballozni.
A gárda a polgárháborút követően is az első osztályba került, ám hamarosan kiesett onnan, és csak 1999-ben verekedte vissza a legjobbak közé magát. Az idő tájt Vucinic már a tartalékok között futballozott, ahol olyan jó teljesítményt nyújtott, hogy többször is felhívták az első csapat keretébe az akkor még alig 16 esztendős támadót.
Az ifjú titán egy nappal a 16. születésnapját követően már az első gólját is megszerezte a szerb élvonalban, a bajnokság nyolcadik fordulójában a Sartid Smederevo ellen csereként beállva volt eredményes, és a pontvadászat során még nyolc alkalommal vetették be.
Vucinic további két gólt ért el, a csapat pedig hatalmas meglepetésre az ötödik helyen végzett. Pedig a mezőny meglehetősen erős volt, a többi csapatban olyan csatárok kergették a labdát, mint például Mateja Kezman, Mihajlo Pjanovic, vagy a jelenleg a Vasasban futballozó Petar Divic. A niksicsiek legeredményesebb támadójának neve is ismerős lehet a magyar drukkerek számára, Vucsinics csapattársa volt ugyanis az a Szasa Branezac, aki később az MTK-ban is megfordult.