To me the easiest way to find velvet is to loot and burn a Swadian village, I often get a single velvet from 1/5 of the looted Swadian villages.
(Due to them being rather expensive +1000 denars, and rare).
Don't know if it's the Swadian villages that hold them, they're just the ones I tend to burn. =)