Vukotić je zbog ubistva Duška Boškovića u Prčanju bio osuđen u Crnoj Gori na 20 godina zatvora, ali je bio nedostupan crnogorskim vlastima
Vukotić je, inače, bio označen kao izvršilac prvog mafijaškog ubistva u Beogradu u klubu „Nana“ u martu 1990, kad je likvidiran Andrija Lakonić.
Uhapšen je na madridskom aerodromu početkom 2006. na osnovu potjernice Interpola koja je izdata u Belgiji, zbog sumnje da je po nalogu Državne bezbjednosti ubio političkog emigranta i višestrukog špijuna Envera Hadrija u toj zemlji.
Belgija je pristala na izručenje Vukotića Srbiji pošto je on u tom momentu imao prebivalište u Novom Sadu.
Izručenje Srbiji je istovremeno značilo da on ne može da bude dalje izručen nekoj trećoj zemlji, pa je Viši sud u Novom Sadu, a potom i Apelacioni sud odbio zahtjev Crne Gore da Vukotić bude predat crnogorskim organima.
Odmah po ekstradiciji Vukotić je počeo s izdržavanjem kazne koju je dobio u Crnoj Gori, ali mu je na ljeto 2009. pozlilo u zatvoru i prebačen je u Institut za kardiovaskularne bolesti u Sremskoj Kamenici, gdje je operisan.
U aprilu 2011. novosadski sud obustavio je izdržavanje kazne jer je usvojen Vukotićev zahtjev za ponavljanje postupka.
3. septembra 2012. u Novom Sadu počelo je novo suđenje za ubistvo Boškovića.
Jedan od najozloglašenijih kriminalaca bivše Jugoslavije otad se brani sa slobode.
Javna je tajna da je Veselin Vukotić bio pod zaštitom moćnih krugova iz srpskih bezbjednosnih službi.
