We had this colleague who never wanted to go to a restaurant with us because she was Vegan... Someone told her to bring her own food and still come with us and she did. Whenever a restaurant refused her to get her own food out of her back-pack, we all got up and left.
If the restaurant pointed out they had Vegetarian options, she educated them what they could do to make these Vegan and she still got her own food out of her back-pack.
We kept doing this for quite a while and our first success came one day when the local Italian had changed his menu to have some Vegetarian menu items have a Vegan option as well. (Naturally when our Vegan colleague was not present). We went back of course and she now takes some of her Vegan friends there too when we're not necessarily around and the chef actually thanked us for letting him know how easy it is to add Vegan options to his menu!
In the mean time, we've given up on the restaurants that are hard-core anti-Vegan and even go to a Vegan restaurant every now and then and then some of us get their meat out of their backpack to sprinkle the Vegan dishes... :-)
Note: She's a raw Vegan...