As part of the very small population of vegetarians of Tokyo (at one time), I can field this.
She's going to have to ask dilligently if things have meat. Even if it's a vegetable dish, with meat written no where near the description (in any langauge) there's a chance it will have meat. I ordered a Vegetable Grautin one time... filled with ground beef for some strange reason. :/
Her safe bets are pasta, and there's tons of Italian restaurants in Tokyo.
Sonoma is a restaurant owned by a couple of buddies of mine. They've got a couple of vegetarian-friendly dishes. The deserts are incredible. It's located in Shibuya.
Fujimamas has been around for a long time. Also gaijin-owned and operated, it has several vegetarian dishes. The Black Bean Chili is absolutely fantastic.
Next to Fujimamas and new to Japan his Good Honest Grub. Some nice veggie dishes. She can google for addresses.
Almost anyone working in these restaurants are bilingual.
Pita the Great is a favorite sandwhich joint. It's fast food (take out only, unless you want to eat on the porch) but all their sandwhiches are vegan. Very tastey, and very inexpensive. It's located in Akasaka, near the Akasaka Byouin (hospital). In looking for this site, I found
this tokyo veggie page which looks quite useful. Wish I knew about it when I lived there. :|