Som 39-årig i 1998 stoppede Veje formelt sin aktive karriere for at blive fuldtidstræner. Første stop var i den tyske topklub [[SG Flensburg-Handewitt]], hvor han stod i spidsen til [[2003]]. Han tog derpå tilbage til Danmark for at blive træner i [[Århus GF]], som han førte til sølvmedaljer i [[2005]] og ottendelsfinalen i [[EHF Champions League]] året efter. I betrængte stunder med mange skader tog han endog selv håndboldskoene på og gik på banen i enkelte tilfælde for klubben, men i sin sidste sæson fik han helbredsmæssige problemer og var sygemeldt i en periode. Han fik derpå ophævet sin kontrakt i sommeren 2009. Efter godt et halvt år var Veje igen klar til at tage en tørn som træner for Århus Håndbold (nyt navn for Århus GF), som efter dårlige resultater under hans afløser [[René Hamann-Boeriths]] havde fyret denne. Til sæsonen 2010-11 måtte klubben af økonomiske årsager skille sig af med flere profiler, men alligevel lykkedes det Veje at få holdet til at spille med i ligatoppen samt nå pokalfinalen.
Levende_personer