I never had a problem with Velius actually. So long as I can get by Wiegraf. He kicks my ass alot. That is until I started using a Lancer against him, then he is a breeze.

I just use Holy and Bahamut with a Short Charge. Easy day against Velius.