Most salmon (and tuna) used in sushi has been previously frozen. So YES, frozen salmon of high quality exists. The problem is that the freezing process (if you want to maintain quality) is complicated. If done incorrectly you wind up with spongy watery tasteless salmon.
So:
Buy it frozen from people who really know how to freeze correctly, those who intend the fish to be good enough for sushi.
eg: http://www.stormseafood.com/
or
http://www.catalinaop.com/Salmon_Sake_s/114.htm
If you find it in a store it should be in it's own deep-freeze cooler, and you should bring a cooler to the store with you. Any changes in temperature and you wind up with spongy fish.
Thaw it yourself using correct thawing methods.
this will ensure freshness, texture (if frozen correctly), and safety.
Thawing should be done
in ice water for a quick thaw or 24 hours in fridge for a slow thaw.
My local grocer carries little bricks of salmon from storm seafood, and following the advice above, I can bring it home and eat it raw. Great texture and flavor.