I see three easy ways to handle this:
- Explain the situation
- Offer to pick the restaurant
- Find alternatives to eating out
As long as your boss understands the reason for not accepting outright, and you make an effort to find a way to make it work out, you shouldn't have a problem.
Above presumes your boss is a reasonable person.
Explain
If you can give a good explanation ahead of time, it will go a long way to making other people be accommodating:
Hey boss, thanks for the invitation! I would love to go out, but as a vegetarian it may restrict our options on where I can eat.
Offer to do the Legwork
Since many non-vegetarians have little experience knowing what the heck your dietary restrictions really mean, offering to do the hard work yourself could help:
There are plenty of restaurants that serve vegetarian dishes and meat too. Do you mind if I suggest a restaurant? Do you like Indian* food?
* Indian is just an example because they usually have vegetarian dishes, but regardless of what you stick in here, try to pick something that your boss is likely to be happy with to increase chances of saying yes. I just love Indian food.
While you may not eat out much because of your diet, you should definitely put effort in to finding restaurants that are enjoyable to both omni- and herbivores for work-related functions, as well as for business dinners and the like.
Offer an Alternative
Maybe there's no restaurant that suits everyone within a reasonable distance from your work. That's fine. Sometimes it won't work out and you can say, "Do you mind if I reschedule and we can do lunch some other time?"
Then go and figure out how you can find a compromise. Perhaps you can offer to get everyone sandwiches and eat outside somewhere. If you're a good cook and think you can make them something vegetarian they'll like, offer to bring in lunch for them sometime. Or if food is just going to be a difficult sticking point, you can try to swap out business lunches for after-lunch drinks or the like so that you can still have the semi-social atmosphere without the issue with food.