I haven't used velocity, but I have used its very close cousin WebMacro. velocity was originally a splinter project of WebMacro, and they still have more similarities than differences. I have several projects which use or have used WebMacro (and page templating in general). I find WebMacro (and Velocity) work better with XSLT styling than JSP does.
We use Velocity templates in a few parts of our online app (in production now for over 6 months) and have found it work quite well. We have templates for system generated e-mail, and for formatting data the user downloads from our site. Use it!