This question has puzzled me for a long time. There is already a question like this on Physics.SE. John's answer to the question seems quite satisfying. But when I googled the cause I found this and this explanation. They maybe wrong but I think How Stuff Works is a reliable source.
And here's the original paper.
I am quite confused now reading the different explanations. Can anyone please shed some light on the issue?
Answer
To start with, "water freezes faster when it starts out hot" is not terribly precise. There are lots of different experiments you could try, over a huge range of initial conditions, that could all give different results. Wikipedia quotes an article Hot Water Can Freeze Faster Than Cold by Jeng which reviews approaches to the problem up to 2006 and proposes a more precise definition of the problem:
There exists a set of initial parameters, and a pair of temperatures, such that given two bodies of water identical in these parameters, and differing only in initial uniform temperatures, the hot one will freeze sooner.
However, even that definition still has problems, which Jeng recognizes: first, there's the question of what "freeze" means (some ice forms, or the water freezes solid all the way through); second, the hypothesis is completely unfalsifiable. Even if you restrict the hypothesis to the range of conditions reasonably attainable in everyday life, to explain why the effect is so frequently noted anecdotally, there's literally an infinite number of possible experimental conditions to test, and you can always claim that the correct conditions just haven't been tested yet.
So, the fact that the internet is awash in a variety of different explanations makes perfect sense: there really are a bunch of different reasons why initially hotter water may freeze faster than initially colder water, depending on the precise situation and the definition of "freeze" that you use.
The paper you link to, O:H-O Bond Anomalous Relaxation Resolving Mpemba Paradox by Zhang et al., with results echoed by the HowStuffWorks video, attempts to solve the problem for a very specific sub-hypothesis. They eliminate the problem of defining freezing by treating freezing as a proxy for cooling in general, and directly measuring cooling rates instead. That experimental design implicitly eliminates one internet-provided explanation right off the bat: it can't possibly be supercooling, because whether the water supercools or solidifies when it gets to freezing temperature is an entirely different question from how quickly it cools to a temperature where it could freeze.
They also further constrain the problem by looking for explanations that cannot apply to any other liquid. After all, the Mpemba effect is about why hot water freezes faster; nobody is reporting anomalous freezing of, say, hot alcohol. That might just be because people freeze water a lot, and we don't tend to work with a lot of other exotic chemicals in day-to-day life, but choosing to focus on that restriction makes the problem more well-defined, and again implicitly rules out a lot of potential explanations ahead of time- i.e., it can't have anything to do with evaporation (because lots of liquids undergo evaporative cooling, and that's cheating anyway 'cause it changes the mass of the liquid under consideration) or conduction coupling to the freezer shelf (because that has nothing to do with the physical properties of the liquid, and everything to do with an uncontrolled experimental environment, as explained by John Rennie.
So, there really isn't just one answer to "why does hot water freeze faster than cold water", because the question is ill-posed. If you give someone a specific experimental set-up, then you can get a specific answer, and there are a lot of different answers for different set-ups. But, if you want to know "why does initially-hotter water cool faster through a range of lower temperatures than water that started out at those lower temperatures, while no other known liquid appears to behave this way" (thus contributing to it freezing first if it doesn't supercool), Zhang has your answer, and it's because of the weird interplay between water's intra- and inter-molecular bond energies. As far as I can tell, that paper has not yet been replicated, so you may consider it unconfirmed, but it's a pretty well-reasoned explanation for a very specific question, which is probably an influencing factor in a lot of other cooling-down-hot-water situations. There is a follow-up article, Mpemba Paradox Revisited -- Numerical Reinforcement, which provides additional simulation evidence for the bond-energy explanation, but it can't really be considered independent confirmation because it's by the same four authors.