I didn't dig in completely, but I'm pretty sure that your problem here is conflating a sort of logical interpretation with a computational interpretation. For example just take your very last example:

{Normalize[ReIm[0]], Normalize[ReIm[z]] /. z -> 0}

Let's walk through piece by piece:

ReIm[0]
(* {0, 0} *)

Normalize[ReIm[0]]
(* {0, 0} *)

Presumably that was all expected. Now...

ReIm[z]
(* {Re[z], Im[z]} *)

Normalize[ReIm[z]]
(* {Re[z]/Sqrt[Abs[Im[z]]^2 + Abs[Re[z]]^2], Im[z]/Sqrt[Abs[Im[z]]^2 + Abs[Re[z]]^2]} *)

Normalize[ReIm[z]] /. z -> 0
(* {Indeterminate, Indeterminate} *)

In other words, these two expressions may seem logically equivalent, but the evaluation engine has to follow its rules of computation, and in this case that leads to different results.

So now consider

FindInstance[ReIm[Sign[z]] != Normalize[ReIm[z]], z \[Element] Complexes, 3]

That's really

FindInstance[{Re[Sign[z]], Im[Sign[z]]} != {Re[z]/Sqrt[Abs[Im[z]]^2 + Abs[Re[z]]^2], Im[z]/Sqrt[Abs[Im[z]]^2 + Abs[Re[z]]^2]}, z \[Element] Complexes, 3]

And those are indeed different when z is 0.