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.

We are creating an antenna that has tight packaging constraints. When the antenna is in transit, the wires are wrapped around the mandrel. For use, the packaging cap gets pulled, and the wires are expected to spring straight. This is a one time use thing. The wires do not need to be wrapped back around the mandrel after the deployment. Permanent deformation limits the effective cone length and cone angle of the antenna. The wires also need to be a certain length for performance reasons.

jsy211: A few questions.
1.Why do you need such a high strength wire? Is it because you are trying to eliminate plastic deformation or do you need the strength for structural purposes?
2.Rather than eliminate plastic deformation, which I don't think you can, why not use a very plastic wire, such as copper, which can be be formed many times without need for annealing?
3.Does it have to be wire? Try thinking in terms of a flat spring, such as you would find in a tape measure. Would that work?
Interesting problem.