Hi all!
I saw the thread on something close to home and decided to jump in. I live in Tokyo and, of course, shirataki are all around. They are not made of soy (or tofu). They are made from alum root and, yes, are considered a noncaloric food, so I guess a condiment (don't know about the starch though). I wish you all could read the recipe pages in Japanese because there are many of them and shirataki is featured in a lot of diet dishes these days. You can also get them dried, which would be easier and you could even import them for those of you not living where they're sold. They need to be boiled a bit before you eat them (at least the hydrated ones). If anyone really wants to know some recipes, I could translate some for ya.