Essentially, there are two effects going on.
1) Breaking a phosphodiester bond between the Pi and ADP to form a new P-OH bond. Although the bonds being broken are somewhat chemically similar, this step is enthalpically favorable in large part because you are relieving the electrostatic repulsion between the negative charge on the terminal gamma phosphate and the neighboring two negatively charged phosphate groups in ATP.
2) The reaction is also entropically favorable because the cell maintains a relatively high ATP/ADP ratio.
I would agree with you that it is incorrect to say that the Pi-ADP bond stores energy. It is more correct to say that the Pi-ADP bond is a very unstable bond (high potential energy), so breaking that bond and replacing it with another more stable bond (low potential energy) results in the release of energy. In organic chemistry terms, the gamma phosphate is a good leaving group.