First of all, it turns out a stationary magnet can't levitate over an ordinary metallic surface (and by "metallic," I assume you mean "ferromagnetic" or something like that); it turns out getting stable magnetic levitation requires either superconductors, some kind of feedback mechanism (like a computer controlling an electromagnet), a diamagnetic material (that's a material which is repelled by magnetic fields, instead of attracted to them), or motion (like a spinning, magnetized top).

Each of these mechanisms of levitation works on a different principle, but I don't think any of them get at the crux of your question. In short, it seems like you're asking for a fundamental, quantum mechanical picture of how the electromagnetic interaction works. It's true that we (physicists) often say that photons mediate the electromagnetic force via the exchange of virtual photons between electrical charges, but this isn't "fundamentally" true. The picture of virtual photon exchange comes from quantum field theory, where we use pictures called Feynman diagrams to describe the interactions between particles. These Feynman diagrams are where the notion of virtual particles comes from, but the important thing to bear in mind is that the "real" physical phenomena correspond to adding up an infinite number of these Feynman diagrams. While the picture that the Feynman diagrams give us is very useful, we should really think of them as an approximation to the "true" physics, and not as a description of what's fundamentally going on.

So, if the virtual particles in Feynman diagrams are only an approximation, what's the "true" physical picture? Well...we don't know! To understand what's "really" going on in the physics, we'd need to be able to solve quantum field theory exactly. But the whole reason we use Feynman diagrams is that solving problems in quantum field theory exactly is notoriously difficult (and often impossible), so we make do with the approximate approach that the Feynman diagrams provide us.

So unfortunately I can't give you an exact answer. I can tell you that for macroscopic objects like a magnet, there's absolutely nothing wrong with ignoring quantum mechanics and just thinking of classical (i.e. non-quantum) electromagnetic fields and ignoring the issue of virtual photons entirely. If you do want to think of virtual photons, I can tell you that these virtual photons do not need to have positive mass or energy, so you don't need to worry about energy conservation (that's what it means for a particle to be "virtual").

Anyway, I'm sorry I couldn't give a better answer, but you're really pushing at the limits of our current knowledge! Good question!