Unfortunately, the tensile strength that you are quoting is not going to be available in any other type of spring steel wire. Chrome-silicon spring steel (ASTM A 401 for commercial quality and ASTM A 877 for valve quality) is only guaranteed to 325 ksi tensile for a wire diameter of 0.032 inches (CQ) or 330 ksi for 0.020 inches (VQ). It's possible that tire cord grades may be stronger than this, but I don't know how readily available they are outside of the major automotive suppliers.
Out of curiosity, why are you wrapping the wire around a mandrel if you do not want it to maintain that shape? Perhaps I am missing something here, but you are using what I consider to be the strongest commercially available steel wire, and it is still deforming. Why can't you wrap it around a larger diameter if you don't want permanent deformation? Alternatively, why is permanent deformation undesirable? You may find it easier to address these issues than to locate a higher strength grade of steel.