The Gemara in Masechet Avoda Zara (p.39) states that kosher meat handled by a non-Jew, without the presence of a Jew, requires a "Chotam B’toch Chotam" (double seal) to insure that the meat received is the original kosher meat and has not been switched by the non-Jew with the more inexpensive non-kosher meat. The question is raised whether fish also requires a double seal. For example, if a non-Jewish courier delivers a fish order to a Jew.
When it comes to fish, The Halacha is more lenient, since kosher fish are easily identifiable. Therefore, if the fish still has the scales on it, it is kosher. Even if the second identifying sign, fins, has been removed, it is permitted, since the Shulhan Aruch (YD 83) rules that one sign is sufficient. However, if the scales have been removed, the fish reverts to the same status as meat and requires a double seal.
SUMMARY
Fish handled by a non-Jew does not need a double seal, if the scales are still present.
