Why does warm water sink? It is well known that water at 4C is denser than water at 0C. This is the usual explanation for why a body of water freezes from the surface (also it's because ice is even less dense, but that's beside the point).
So let's consider a body of water that has recently frozen over. I imagine, that nearest to the ice crust the water is at 0C and as one goes downwards, the temperature rises up to 4C (until we get close to the lake bed where the ground is a heat source). This implies, that there is a particle density gradient (higher particle density at the bottom) and a temperature gradient (highest average kinetic energy of particles also at the bottom).
But if that is the case, there must be a flux of water molecules directed upwards.
EDIT
As per Floris' suggestion, I include here some reasoning behind this.


*

*The kinetic energy of a water molecule at 4°C is higher than at 0°C by an amount that corresponds to a height difference of 200-300 meters. One would expect this extra kinetic energy to easily overcome the gravitational potential.

*Of course the above treats liquid water like an ideal gas, which is obviously invalid. An explanation came up, that as a molecule moves to a region of lower particle density, it has to break hydrogen bonds and loses energy on this process. However, this is not correct. Hydrogen bonds are the reason for a lower density of water at 0°C. Moving to a region of lower temperature is favorable, as more hydrogen bonds should be formed, lowering the overall energy.

*My intuition suggests, that hydrogen bonds inhibit the motion of all molecules, warm and cold and prevents mixing in general, much like two regions of a solid crystal do not diffuse into each other. This might allow hydrogen bonded clusters of molecules to act somewhat like macroscopic objects.

*But if hydrogen bonds play such a role, shouldn't the energy gained by moving to a region of colder water still drive mixing?  
END OF EDIT
The original question read:
So why is it, that water seems to obey the macroscopic laws of Archimedes' principle, rather than rapidly mixing, as a microscopic analysis would seem to suggest?
After the discussion in the comments (outlined in the bullet points above), I am looking for a more detailed microscopic description. Though hydrogen bonds are clearly the main player here, as the 3rd bullet point says, there's energy to be gained by moving to a region of lower temperature. Perhaps there is a potential barrier to overcome, i.e. a molecule first needs to break some bonds, before moving and forming even more of them, but how big then is that barrier?
 A: Very interesting question.
As you wrote yourself in your Edit it is hard to describe water via the ideal gas model.
You have to introduce at least two important improvements of your ideal gas:


*

*Dipole - Dipole - Interaction instead of no interaction. Let's call this pair potential $V_d$ and note that for two given molecules $V_d$ is not only distance but also angle dependent.

*Describe water molecules as QM rigid rotators instead of hard spheres.


Because of $V_d$ a certain alignment of water molecules is favoured. The rotation of the molecules which increases with Temperature $T$ "works against this" alignment. This state averaged $V_d$ is called Keesom-Interaction. Let's call it $V_k$ and note that $V_k \propto \frac{1}{T}$.
Up to this point we introduced a model that predicts qualitatively stronger hydrogen bonding and more regular alignment for deeper temperatures.
Now let's take a step back from liquid water and look at ice.
In this lattice we practically eliminated the rotational degrees of freedom of the individual molecules (and gained 3 modes of vibration each). 
This means if we want to minimize $V_d$ we bring the water molecules into a certain structure and they stay this way. 
It is important to realize that (in difference to e.g. salt lattices) minimizing the distance between atoms (and in the macroscopic scale the density) alone does not minimize $V_d$. Taking the angle dependencies of $V_d$ into account can increase the Volume as happening in the case of water/ice.
The cold but liquid water between 0° and 4° in the upper layers of your lake is not cold enough to form a lattice but has more locally ordered structures than the water at 4° or above. Besides the Keesom - Interactions $V_k$ are stronger 

It is important to realize that (in difference to e.g. salt lattices) minimizing the distance between atoms (and in the macroscopic scale the density) alone does not minimize $V_d$. Taking the angle dependencies of $V_d$ into account can increase the Volume as happening in the case of water/ice.
The cold but liquid water between 0° and 4° in the upper layers of your lake is not cold enough to form a lattice but has more locally ordered structures than the water with 4° or higher, because the Keesom - Interactions $V_k$ are stronger and more important. This local ordering because of $V_k$ also explains the lower density compared to the water at 4°. (Taking angle dependency into account again).
Now after all this introduction what happens with your water molecule that comes with its high velocity to an upper layer. As you wrote it can easily overcome the gravitational field. Somehow it looses its translational energy and other molecules now move or/and rotate faster. We also can reverse this process and look at a slow molecule from the 0° layer that goes down and becomes accelerated in the 4° layer. 
Macroscopically this heats up the upper layer and cools down the lower layer until equilibrium is reached.
The famous lake in the winter is not a closed system. You constantly heat from the floor and cool it from the air. 
This is comparable to a "normal liquid" where you constantly cool from the floor and heat from the air. Also in this case you would get two layers.
If you heat and cool with the same rate it is possible to get a steady state that does not change, although it is not in equilibrium.
The important question is, what happens if you stop heating or cooling. Here your questions becomes important and leads to the prediction that water will equilibrate quite fast. To say it in another way, we expect water to have a high thermal conductivity. Now if you look at this table. 
You get some nice data for thermal conductivity. I made a plot out of it which makes this point pretty clear if you keep in mind that the red bar shows the mean and the leftmost point represents water:

Perhaps it is also nice to note that the substance with $\lambda = 0.5\rm \, W\, m^{-1}\, K^{-1}$ is ammonia. This compound also has significant dipole dipole interaction.
