There's no energy "stored" in magnets, magnetism is not energy
The energy density of a field is:
\[ e = \frac{B^2}{2 \mu_0} \]
Integrate over space to get the energy stored in the magnet.
Another way to put it: the magnet has a large hysteresis loop in its B-H curve; the area of this curve corresponds to the energy dissipated in going around said loop. If you used it as a transformer core, that would be its core loss every cycle.
I think it's going to be a "what happens when you short a charged capacitor into a discharged capacitor" situation, i.e., half the energy goes into actual heat, the other half goes into energy in the field. The magnetic version of charge is flux, which is conserved, but the energy is divided.
The funny thing is, perpetual motion types most likely aren't clever enough to figure out how to extract incremental energy from a magnet. I'm not even quite sure how you would do that; doing it passively would be difficult (demagnetizing it with an electromagnet will only consume more power), maybe you'd resort to heating it above Curie temp, demagnetizing a bit at a time.
But you need to be careful that you aren't using it as a boring old heat engine -- there is a strong tempco and some recoverable magnetization as long as T < Tc, and this variation could be used to repeatedly convert change in temperature into change in flux density.
Tim