I understand about the labelling. I say I'm vegetarian, but I'll eat fish. The first time I was in Kyushu, I explained that at one restaurant (the kind where you don't order, they bring you stuff).
They brought me a plate of raw horse meat. (And 'begetarian' is a Japanese word. The idea may be different on that island... Maybe they thought I only ate vegetarian animals?)
Countless places have assumed that meat broth was fine, so just removed the pieces in soups. All over the world.
Whatever you do, though.. don't order a special vegetarian meal on Air Canada. The last time I did that, they gave me a block of uncooked cold tofu. With some nasty sweet sauce. You're better off picking out the stuff you can eat from a regular meal...