It isn't obvious that one must be certified to advertise your product as "Kobe Beef" in the United States. The designation "Kobe Beef", in theory, is supposed to operate a lot like a trademark, but it is a geographic designation that presumably belongs to officials from the geographic area, rather than a true trademark that is owned by a private individual or corporation. It is one thing to state you have "certified Kobe Beef" when you don't and another to say merely that you have "Kobe Beef" in a place where no certification is required by law and the term is not well defined.
The United States frequently does not honor foreign law procedures necessary to establish a geographic designation. As another example, the U.S. routinely tolerates the marketing of "champagne" in the sense of a generic term for sparkling wine, even though it is regulated as a geographic designation for sparkling wine made in a particular manner in a particular place within France when used in the European Union.
The handful of geographic designations that are treated as enforceable under regimes like the ones for Kobe Beef and Champagne arise under U.S. specific laws. For example, federal law (strictly speaking a federal regulation promulgated pursuant to federal law) mandates that the term Bourbon whiskey refer to a product made at least 50% of distilled spirits made in a certain way in Kentucky.
There are deceptive trade practices laws in many states that require designations of origin to be truthful and the Lanham Act also prohibits false advertising. But, to the extent that beef originates from the Kobe vicinity (i.e. Hyōgo Prefecture) in Japan but is not certified Kobe Beef under the Japanese geographic designation laws, this would not violate either of these laws because the geographic designation is accurate.
Hyōgo Prefecture where certified Kobe Beef comes from is shown in red on this Wikipedia map.
Alternatively, the sellers of Kobe Beef could argue, probably with a good chance of success, that in American English the term "Kobe Beef" refers not to "certified Kobe Beef" or even to beef actually produced in Hyōgo Prefecture, Japan as a geographic designation, but to beef with some important qualities of certified Kobe Beef, without regard to where it is actually made, for example, using the same breed of cow raised so that it has a similar level of fattiness. I would guess that hundreds of places in the U.S. sell "Kobe beef".
In the same vein, "Kentucky Fried Chicken" does not mean chicken fried in Kentucky in American English, instead it means chicken fried in the style made famous in Kentucky, a Philadelphia Cheese Steak in American English means a sandwich made in the style of cheese steaks sold in Philadelphia and not a sandwich actually made in Philadelphia, and a Boston Cream Pie in American English means a cream pie made in the style of pies made in Boston and not a pie made with cream that is actually produced in Boston.
U.S. law, in general, and American language conventions as well, are quite hostile to the notion that what other countries might consider a geographic designator does anything more than describe a style of making food as opposed to making a true statement regarding place of origin. In American English an unambiguous statement regarding place of origin would normally be made with a statement like "Made with beef imported from Kobe, Japan" as opposed to a mere product description of "Kobe Beef". The inference one makes that "Kobe Beef" is certified Kobe Beef from Kobe, Japan is probably an unreasonable assumption and certainly the question would be a disputed question of fact on falsity that a court could reasonably rule in favor of the restaurant upon. (Similarly, if you say you are headed to "my house" you aren't necessarily implying that I own the house, merely that it is associated with me in some way.)
Also, to quantify damages, one would have to determine the difference between the fair market value of fine beef in a fancy restaurant that is not certified Kobe Beef and certified Kobe Beef as you would have to in order to prevail and win damages in a lawsuit like that one, is non-trivial and might determine that, for example, the alternative still charges $300, greatly reducing damages. And, the number of meals involved still probably isn't huge, perhaps in a thousand per year. So, maybe the damages if someone prevailed might be $150,000 for all meals sold in the period covered by the statute of limitations even if one could successfully prove that in a class action lawsuit.
It is also possible that no one has decided to take any action to enforce what is a violation of the law, even to the extent that it is indeed a deceptive trade practice. It isn't economical to sue over a single $350 beef purchase, particularly when there are non-frivolous defenses of the type that I have identified. People who purchase this kind of meal aren't easy to identify in order to bring a class action that could lead to a more viable lawsuit, particular as the patrons might be spread all over the world.
The New York State attorney general might decide that it has higher priorities than suing a business that is getting people to willingly and happily pay $350 for an entree at a single restaurant that mostly benefits the nine certified Kobe Beef restaurants. And those nine restaurants may likewise have decided that it wasn't worth suing under the Lanham Act because even if they prove false advertising which is causing patrons there to pay $50 more than they should per entree, it isn't at all obvious that this caused any damage to the restaurants in question that couldn't be solved with more advertising of their own.