[czucha]

It's pretty easy - I've been veggie in Tokyo for nearly 9 years - Happy Cow have a good list of veggie spots, and there's this:

Metropolis - Local Flavors - Green Scene

(look for 'green scene' in the archive)