Velvia is a very narrow film, meaning that in my experience even 1/2 stop can mess up a shot. So depending on how you're shooting, it could work for or against you...it's also quite slow. I would shoot Vevlia 50 at 64 or 80 and 100 and 125. Provia on the other hand seems to be more forgiving and you really only lose a little punch in terms of saturation if slightly underexposed as well. Provia.....uh...shhhhh (scans really easily)shhhhhh....
Why not try some of the Kodak offerings as well? The E100VS is a great film and has some serious punch and contrast to it. It seems to handle easier than the aforementioned Velvia as well.
Just my $.02