2005 zog Verheyen, bereits Sopransaxophonist im Saxophon-Quartett Saxkartel, für ein Jahr nach Paris, wo er zu Bands von Giovanni Falzone, Remi Vignolo, Nelson Veras und Bruno Angelini gehörte. Zudem war er Mitglied des Belfin Quartetts, dem neben ihm und dem Bassisten Joachim Florent als Belgier die Finnen Aki Rissanen (Piano) und Ville Pynssi (Schlagzeug) angehören. Während seiner Zeit als Artist in Residence in seinem Geburtsort 2006/2007 gründet er ein internationales Quartett mit Bill Carrothers, Nicolas Thys sowie Dré Pallemaerts, mit dem er zwei Alben einspielte. Auch mit seinem Narcissus-Quartet veröffentlichte er zwei Alben.
Im Juli 2004 wurde er bester Solist sowohl beim baskischen Gexto Jazz Festival als auch beim internationalen Wettbewerb Jazz Hoeilaart. Im Folgejahr gewann er den Wettbewerb als Nachwuchstalent in Gent. Saxkartel erhielt 2006 den Preis der Jury beim Tremplin Jazz in Avignon. Im selben Jahr gewann das Belfin Quartett beim Wettbewerb von La Défense den Preis für die besten Kompositionen. 2008 wurde er mit dem belgischen Django d’Or als „neues Talent“ ausgezeichnet.
