A simple experiment. Make an electric magnet as strong as a regular refrigerator magnet such that either can affix to the side of a refrigerator and both hold an equal mass with any required dead-weight.
Where and what is that question mark?
This is clearly not a "stable" system since if you turn off the electric magnet, stuff is going to fall.
The magnetism of permanent magnets comes primarily from the fact that electrons have a quantum-mechanical property called spin. (Despite what this word suggests, they are not actually rotating on an axis like the Earth does.) Any charged particle with spin acts like a tiny magnet. (It is said to have a “magnetic moment”, which measures its amount of magnetism.) In a ferromagnetic material, the spins align and create a significant macroscopic magnetic field.
Electrons cannot stop “spinning”, and it takes no energy to keep them “spinning”. Their spin is just a kind of intrinsic angular momentum that they possess. So permanent magnets don’t need any power source. A ferromagnetic material can lose its macroscopic magnetism if its spins become non-aligned, but an electron can never lose its tiny magnetic moment.
The actual mechanism for how the permanent magnet works is not actually that important here (we'll come back to it though). What is important is the definition of work:
$dW = \vec{F} \cdot d\vec{r}$
If you look at it, you see that whilst to hold up an object does require a force to balance gravity, it does not take any work because the object isn't moving. Ultimately this is the answer to your question: it's just not required that energy be expended to supply a constant force and its not a paradox if this happens.
OP raises a good point that if we used an electromagnet to supply the force we would need to continually provide energy to it. A permanent magnet on the other hand would not. A similar situation is that if a human held the object they would get tired, but if we simply hung the object from a string or placed it on a table no more energy needs to be supplied. This simply reflects that some ways of generating constant forces are not energy efficient. An electromagnet only functions whilst there is a current flowing and you will get continuous Joule heating because of this. A human's muscles cannot stay contracted for long periods of time and lose energy in cycles of contraction/relaxation. Conversely, the permanent magnet has no such mechanism to lose energy since its magnetism comes from the alignment of fundamental magnetic dipoles that cannot be demagnetised, only realigned and so can produce a continuous force without needing an energy supply.
