The thing to remember is that he does get destroyed before being reanimated. That means he is discarded and all cards and tokens attached to him get discarded as well. Then when you reanimate him, it is akin to summoning him fresh all over again.
However, if you are referring to [mwcard=DNC12]Shaggoth-Zora[/mwcard] as I suspect you are, then you actually made a rules error. You can not make a Legendary creature into your Eternal Servant.