Eating vegetarian in Japan is hard. I gave up eating vegetarian in restaurants pretty soon after I arrived here (and gave up eating vegetarian at all after I got married ;-) ). A couple of comments:

- In Japan, I have never heard of anyone one using eggs in tempura batter. You can be almost 100% sure that it's OK. So vegetable tempura is a good bet. Probably the most safe is cold soba noodles with tempura.

- Vegetable sushi is only really available at those cheap revolving sushi restaurants. However, when dining with vegetarians this is my go to spot. You are unlikely to find vegetarian options at good sushi restaurants.

- You will never find miso soup or any soup (ramen, etc, etc) in Japan without animal products (apart from the rare exception that I will explain below). Ordering off the menu is likely to cause serious heart attacks in the staff. If you are a regular customer, you can get away with it, but you seriously can't expect to walk off the street and ask that the change the food for you. Which is odd because Japanese customer service (with this one exception) is usually insanely accommodating.

- Although it is remarkably better than when I arrived, Japanese people really do not understand vegetarian cooking. If you ask for vegetarian tempura they are likely to give you extra shrimp to make up for the other fish that you didn't get. If you protest that it isn't a vegetable they will look blankly at you and say, "But it's delicious". Having a moral stance on what you eat and don't eat without it being a religious thing just does not compute. They totally get the non-pork issue for those whose religions don't allow it, for example. When I was teaching English, I tried to educate the students about the word "vegetarian" and in the exam I had the question, "John does not eat meat, fish or eggs. He only eats vegetables. What is John?" One of my students answered, "John is a cow" (to which I had to give him full marks, of course ;-) ).

However, this brings me to the only strategy that worked for me consistently in restaurants. It turns out that Japan has it's own traditional vegan cuisine. It is called "shoujin ryouri". It is a Buddhist way of eating (the "monk training food" noted by the GP). It is composed of very traditional Japanese dishes and is wonderful. Although there is much more to shoujin ryouri than just eating vegetables (and they also avoid alliums like garlic and onions for some reason), it is a word that every Japanese restaurant worker will understand completely. The GP's characterisation of shoujin ryouri as "not intended to be tasty" made me laugh because it is true that it is not intended. However, it is invariably mind-bogglingly delicious. I highly recommend going to a temple that serves it and trying it.

Anyway, usually I would say, "I'm very sorry, but I only eat shoujin ryouri. I know it's completely impossible, but I wonder if there is any way you could make something like that." After getting over the shock that a westerner would eat only shoujin ryuori, the response would inevitably be, "That's incredible. I'm impressed. That's a very difficult way to live" and they will either try to make something for you, or tell you that it is indeed impossible.

Apart from rice (which is a given), the basis of most Japanese cooking is dashi (soup stock). Most restaurants (and homes) use powdered soup stock that already has katsuo bushi (the dried fish flakes) added. In shoujin ryouri they use only kombu dashi (stock made from sea kelp), sometimes with dried mushrooms. If a restaurant has kombu available, they can make dashi and then can usually figure out something. All restaurants have vegetables and tofu hanging around somewhere. If they do not have kombu, then they will be completely at a loss and there is nothing they can do.

I was vegan when I came to Japan (although not ethically vegan -- I just like eating that kind of food). I tried to keep eating that way, but it was pretty difficult (and downright impossible when I had to go to work related functions -- I got a reputation as a hard drinker because I would only pick at my food and drink beer all night ;-) ). Pretty quickly, I started eating things with normal dashi and after about 3 or 4 months just ate whatever anyone else ate at restaurants.

It is not impossible to be vegetarian (or even vegan) in Japan, but it is extremely difficult.