I've found that it is quite easy to be vegan here in Madrid as long as you cook for yourself. I've been here for a lil over 6months. Beware:the restaurants frequently fail to mention that normal veg friendly meals like green beans have bits of ham in them so always ask. But there is an AMAZING buffet style place in Madrid (metro:Anton Martin) called Organic Market and Buffet. Also, if you can stumble upon an Asian fruit store they almost always have tofu, soy milk, seitan, and fresh spices like ginger that you can get for extra cheap.
Be sure to check out a town called Sort.
It is in the pyrenees.
Went there in 01 to see my stepson compete in the World Cup free style kayaking. He placed 3rd.
We also saw some of the tour de france people training there.