Years ago, I read that this was the case in the US, or at least in some major cities. I have since found out that it's not true as a matter of law, but it's pretty common.
The reality is that flash-frozen fish is rarely as good as fresh. There are a couple of important exceptions, the main one being tuna, which takes the deep freezing very well.
What happens to fish when it's frozen is that the texture goes south. In Japan, one of the most remarkable things for a raw fish lover upon first arriving is to discover just how different the textures of raw fish often are. Sashimi is rarely served in thin slices, though there are a few exceptions -- blowfish (fugu) for example is cut very thin indeed. The thickish slices let you get a complicated mouth feel that is distinctive to the fish and often to the cut.
One thing I started to notice in Japan was that freshness was never part of the discussion, part of the rhetoric about sashimi. In America at least, freshness is almost always equated to quality in fish: this fish is so fresh, see it has no fishy smell, it must be good. Nobody says this in Japan. Freshness is a minimum: if it's not fresh, it's not food (setting aside salted fish and stuff like that -- I'm talking about raw here). Whether it's good or not is another matter entirely. So this super-fresh fish, cut in lovely thick sashimi slices, is okay, and this same breed of fish cut the same way is terrific, and of course the former is about 1/5 the price of the latter. The difference isn't freshness: it's other kinds of quality. But once a fish has been frozen and thawed, a lot of what makes excellent fish better than decent fish goes away.
I think that if your use of raw fish is going to be restricted to what has been frozen, you have to give up on radical simplicity. Instead of serving sashimi, completely naked and just garnished to taste with soy, wasabi, sea grapes, and whatever, you've got to move into tartares, ceviches, and tataki, things that are pre-seasoned and at least coarsely chopped. That way the disadvantages of the freezing don't adversely affect quality.
What the EU needs to do, if you ask me, is institute an intensive inspection program for meats (including fish) to be served raw. That will of course crank the prices of the products through the roof, but it's available. This is in a sense the Japanese approach: if you want top quality, it's going to be expensive, so just face that in advance and know that we've done everything we can to ensure that it's worth it. Chicken can be expensive here, sometimes outrageously so, but the good stuff is incredibly flavorful and if you would like to slice it and eat it raw as chicken sashimi you can go right ahead. If there's enough demand for a given product, food scientists will work out methods of more efficient inspection or processing or whatever that will bring the price down, but they're not going to do that unless there's enough demand to fund their research. And so in time it levels out. But the EU, and even more so the US, does not want chicken to be expensive -- so our chicken is cheap and flavorless and full of salmonella. Our salmon is cheap and flavorless and often infested with parasites. It's a matter of choice: we do not have to stand for this situation, but if we want to get rid of the "flavorless and infected" part we will also get rid of the "cheap" part.
Maybe we should start eating less of better ingredients?