Where is the energy lost in a spring? Thinking about springs, and their extensions, I recently came to a confusion which I hope this wonderful community can help me solve.

The question is this. When the block is initially attached to the spring, the spring has some extension $x_0$. Now the spring gets extended to some extension $x=\frac{mg}k$ by an external force maintaining equilibrium at all the points such that $KE=0$ at the bottom. 
As my reference is the line shown in the figure, the initial potential energy $U$ is 0 due to both gravity and spring potential energy($x=0$).
Now as the block comes down, the spring potential energy is:
$U_(spring)=\frac12kx^2$.   Final extension is $\frac{mg}k$. So spring potential energy is $\frac{m^2g^2}{2k}$
But the decrease in gravitational potential energy is $mgx$ which equals $\frac{m^2g^2}k$.
This means that potential energy has decreased. Intitially, $U_{net}=0$ but finally $U_{net}=-\frac{m^2g^2}{2k}$.
Where if any, did this energy get compensated(to ensure COE is still true)?
 A: You're missing a somewhat subtle point in your analysis. The block on the left in your diagram, where the spring is at its equilibrium position, is moving, so it has kinetic energy (which you're currently ignoring). I'll leave it to you to sort out what the speed needs to be and check that CoE holds.
It needs to be moving because, if it were not, then there must be some force (your hand?) holding it in place. This would count as an external force, and when such a force acts, CoE does not hold.
A: The "missing" energy you're referring to actually left the block-spring system when the external force was interacting with the block. One way to think about it is the following.
The work-kinetic energy theorem tells us that, since the KE of the block doesn't change during the lowering process, the net work done on the block is 0:
$$W_{net}=\Delta \mathrm{KE}=0,$$
but the net work done on the block may be written as
$$W_{net}=W_{grav}+W_{spring}+W_{external}.$$
Gravity, the spring, and the external agent (i.e. my hand) are all doing work on the block, and the sum of these must be 0, since KE didn't change. Gravity does positive work, since displacement is in the same direction as the force of gravity. The spring and the external agent do negative work, since their forces are applied in the opposite direction of the displacement:
$$W_{grav}=mgx=\frac{m^2g^2}{k}.$$
The work done by the spring is equal to minus the amount of potential energy it gains (in other words, the spring does negative work on the block, the block does positive work on the spring), so
$$W_{spring}=-\frac{1}{2}kx^2=-\frac{m^2g^2}{2k},$$
and, from the work kinetic energy theorem, we then have
$$0=W_{grav}+W_{spring}+W_{external}\implies W_{external}=-\frac{m^2g^2}{k}+\frac{m^2g^2}{2k}=-\frac{m^2g^2}{2k}.$$
So the external agent does negative work on the spring (or the spring does positive work on the external agent), which exactly accounts for the energy that you noticed that was "missing".
A: Imagine you extend spring from $x_0$ to x by adding a weight, rather than by pushing down with you hand. This will help to illustrate why COE only works if you take all relevant forces into account.
So, you add a weight of mass M to the original setup. Your new equilibrium position is where gravitational force = spring force.
Gravity => F=mg + Mg   (m is the original mass of the block, M is the additional).
Spring => F=kx  so...
kx = mg+Mg 
(incidentally I don't think you can say that kx=mg as you do, mg is not enough force to keep the spring extended at x, mg gets you to x0, the original extension)
But how did we get to this point?  Intuitively you know that if I added a weight of mass M, the system starts moving, it has to move to reach the new extension. Hence there is now Kinetic Energy, which means we are in the wonderful world of harmonic motion unless something stops us...
But your scenario isn't moving (you make this clear in your question).  So something has happened to stop the system. An external force has stopped us (e.g. frictional losses over time). 
This is your missing energy. As another answer has pointed out, an external element (e.g. hand+arm+shoulder etc) has done work to stop the block at extension X.  Or, over time the kinetic energy was lost to friction. Either way, it is gone or stored in external potential energy (see below)
Another way to think about it, is to imagine you have a steel rod holding the weight down - so no hand, no new weight.  In this scenario you'd have potential energy stored in the rod, which will have bent slightly.
