The shininess is determined when you receive the Pokémon back from the scientist. As you said, the gender/nature (and IVs) are different each time you reset. It's all determined by 'Personality Values'.
I wouldn't recommend shiny hunting this way though, since you can breed Anorith/Cradily, it'd probably be easier to just do that. You might want to look into RNG abuse to increase your chances.
Sources: Fossil RNG, Personality Values.