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.