Its known as the Mpemba effect, and there are various theories to explain it.
It is currently believed that water molecules exhibit intermolecular repulsion causing stretching in the covalent bonds between hydrogen and oxygen, and in the hydrogen bonds between the water molecules. The stretching results in energy being stored.
Water at higher temperature has a very slightly lower density so the intermolecular distance is a little longer, and the hydrogen bonds stretch more due to the molecules being further distanced from each other,
The theory (which was developed by Nanyang University in Singapore) is that the hydrogen bonds stretching allows the covalent bonds to shrink back a little, giving up their energy. In effect, this is the same as cooling, and so warm water should in theory cool faster than cold.
Its the more recent theory to explain the Mpemba effect, which was named after the Tanzanian student who first observed it (in relation to freezing of ice cream mixes) in the 1960s.