Salt water fish could possibly have made the trip via train from Seattle, packed on ice, although I'd expect it to be rather expensive.

Smoked salmon also makes very tasty sushi if fresh isn't available. Tamago is an option that might appeal to a reluctant North Dakotan.

Oh, and salmon can be found in some waters of North Dakota; I don't know if they're landlocked or what, but that's an option too.