I'm pretty sure that this Mpemba Effect is folklore. The hot water must necessarily pass through the temperature that the cooler water starts at. In fact if we are to believe this than at some point the initially hot water and the initially cold water must, at some point, be the same (average) temperature. Why then would it start to cool faster?

Options that I can think of
1) initially hot water cools very asymmetrically so some hot portion gives of heat (to the air!) faster
2) more rapid temperature change sets up strong convective currents that, because of momentum, stay around, causing the initially hot water to give up heat faster.

These both seem very unlikely. Fluid water is a very good heat conductor (and air a good insulator) making it unlikely that there would be significant temperature gradients and intuition tells us that freezing water takes much longer than it takes any sort of current to die down. (also note that these two effects would act to cancel each other out)

As for the reasons mentioned in the wikipedia article:

1)Definition of frozen: I suppose that this could account for the effect if you measured the time for cold water to completely freeze and hot water to reach 0 degrees C! But in general as long as you use the same metric this won't matter

2) Evaporation (reducing the volume to be frozen): So an initially hot fluid will evaporate more and I suppose result in a slightly smaller volume to freeze. Since the thermal mass is proportional volume and the heat transfer is proportional to area this is a real effect. However the % change in volume of any reasonable shape of water is so insignificant compared to the difference in energy of hot water and cold water that this effect is almost certainly negligible. (perhaps if the claim was hot water freezes faster than cold water if it is laid out in very very very thin sheets I would buy it because of this.)

3) Convection: see above.

4) Frost: Since the water must pass through the same temperature (0 C) for frost to start to build the frost must grow differently on initially hot water than initially cold. I really see no reason to believe this is the case

5)Super cooling: again, if the convective forces persist for a mush longer time than seems reasonable...

6) Solutes and dissolved gases: I mean if one fluid is a different chemical composition than the other then I suppose all bets are off, but I feel the claim of "warmer water freezes faster than colder water" implies they are both the same substance

However the main reason I believe this to be an Urban Myth is that it makes such a good story. It fits our belief as a culture that there are weird things about science that we don't understand and it challenges our initial intuition in a memorable way. In addition it requires more effort to test than most of us are willing to put forth (including me: I would be very interested if someone would actually do the test recommended in the wikipedia article.) Lastly; hot water freezing faster is a much better story than the other way around. Telling people that hot water freezes faster makes you seem to have some kind of secret knowledge; a spell you can cast over ice cube trays to make them into ice faster.

I bet a reasonable rule for judging truth is that, all else being equal, the better story is less likely to be the true one, because if the truth was also the better story then no one would tell the boring one.