You are asking two questions really
How is PE actually stored in a steel spring at the atomic level?
The explanation for this lies in quantum mechanics
Could you explain in detail how/where potential energy is actually stored in a steel spring and why the material never surrenders to the bending forces taking a new shape?
Replying to 1) one has to think quantum mechanically. All solids form lattices. These lattices are formed because even though the individual atoms and molecules are neutral, there are electrical spill over fields due to the fact that the orbitals for the electrons are not spherical, except for l=0 angular momentum states, but have shapes. One can think of them as LEGO shapes that fit, positive spill over to negative spill over forces, forming new quantum mechanical solutions at a lower energy level, releasing energy into soft photons in the process ( that is why precipitation releases energy/heat to the environment). Thus the lattice is balanced at a lower quantum mechanical level than the free atoms/molecules themselves.
The state function of the lattice is a collective one of all the molecules/atoms that compose it, and acts as a higher level "particle", responds collectively quantum mechanically as long as the energies it interacts with are within the energy levels of the collective state. You must remember that in quantum mechanical solutions the lowest energy levels are filled but the higher ones exist and are available if energy is supplied.
What happens if an external force is imposed on the lattice? The collective state function, solution of the quantum mechanical state of the lattice, by absorbing soft photons collectively, moves to a higher lattice energy level. When the pressure is removed, it falls back to its lower energy level by releasing soft photons. These are non destructive deformations. If the energy is too high the lattice bonds will be broken and the lattice solutions will no longer be valid.
Elasticity means that some materials have enough energy levels to the lattice to be able to be deformed and fall back to ground state without being destroyed. The energy is stored in the higher energy level attained by the interaction "lattice forrce". So the steel spring lattice at the atomic level is at a higher energy level . Evidently steel lattices can take a lot of deformation so must have many higher than ground state energies.
Now for the second question, the models are continuum models with parameters that do depend on the quantum mechanical underlying framework but are emergent, from the many body problem. This seems to be still a research problem as it has to do with materials useful for industry and life in general. Models are proposed which use the spring modeling of the other answer at the lattice level, avoiding the quantum mechanical complications by approximations.
In a lattice spring model (LSM), the material is discretised into particles linked by springs. However, LSMs always adopt linear springs, which results in a stiff approximation of the corresponding elastic solution. In this work, a high order LSM is proposed to overcome this limitation by introducing additional degrees of freedoms (DOFs) to the particles.
In this case the internal quantum mechanics dynamics are approximated by springs.