There is some current legislation going through VA that would allow us to conceal carry in restaurants. Sign up to the VCDL alerts and you'll get notifications and such. There is also a "castle doctrine" legislation that is currently going through the va senate I believe.
I've OC at numerous restaurants and no one seems to bat an eye. There are laws saying it's illegal to CC in restaurants that serve alcohol, but nothing in the books saying OC is illegal so OC is perfectly legal. If the proprietor gives you any lip about it and ask you to leave though, by all means leave otherwise you'll get charged with trespassing charge, but NOT a firearm charge.