A more mundane explanation is that hot water evaporates faster than cold, decreasing its volume and thus the time it takes to freeze.
[Edit - Cannot delete my comment now. As 'ketzo' points out below my point is not same as OP's. OP points out that hot water is less dense. Maybe less dense liquid cools faster]