Is this possible?
no, i thnk there is a law against it
or if there isn't, there should be
A local vegetarian restaurant here in Vienna, VA mentions natto in their list of ingredients:
http://www.crystalsunflower.com/Gormet%20Glossary.htm#NATTO
But when I asked my waiter about it one time, he said nothing on the menu has natto anymore. "My bosses made us take it off," he told me. It probably wasn't popular -- someone should go there and request it.
Make your own. There's an episode of Moyashimon that teaches you how to make it from scratch.