Ok, but slowing down the Moon's orbital speed makes it jump down to a closer orbital distance, that is, the Moon's gravitational energy decreases. So the energy of the tides has actually come from this variation of gravitational energy of the Moon.

Except that, as I understand it, the Moon is drifting away from us.

I sincerely don't know if the Moon drifts away or the opposite. If it drifts away, it loses kinetic energy but acquire gravitational potential energy. The sum of the two, that is the Moon's total energy, increases with increasing distance:

T = kinetic energy = 1/2GmM/R

V = potential energy = -GmM/R

E = total energy = T + V = -1/2GmM/R

where G = gravitational constant; m = Moon's mass; M = eart's mass; R = distance Eart-Moon.

So, in that case, the Moon have to subtract energy from Earth in some way (maybe from earth's spinning energy?).

In any case, all of the orbital energy of the Moon itself derives from the processes that created the Moon (if the theory that the Moon was created by an impact between the Earth and another body, then the orbital energy of the Moon derives from the kinetic energy of that impact).

If you have two bodies with non-zero mass, non-zero tangential relative speed that are approaching, they can form a system planet-satellite where the lighter one orbit around the heavier one. The parameters describing the orbit: distance R and orbital speed V, are defined by the initial parameters of the two bodies: positions and speeds. So you don't need to look for particular ways of generating the orbital kinetic energy.