Interpolation incorrectly depends on order of data points

[Andrew Moylan]

The documentation of Interpolation[list] suggests that its result should be
independent of the order of data points specified in list. This was the case
in version 5.1 (see below). This is not the case in version 6.0.1 (Windows):

Interpolation[
{
{{0, 0}, 0},
{{0, 2}, 1},
{{1, 0}, 2},
{{1, 2}, 3}
},
InterpolationOrder -> {1, 1}
][0, 0]

returns 0, as expected, but

Interpolation[
{
{{1, 2}, 3},
{{0, 0}, 0},
{{0, 2}, 1},
{{1, 0}, 2}
},
InterpolationOrder -> {1, 1}
][0, 0]

returns 3, which is manifestly incorrect given the set of data points
specified (which includes the element {{0, 0}, 0}).

Here is the (correct) behaviour of version 5.1 (Linux):

Interpolation[
{
{0, 0, 0},
{0, 2, 1},
{1, 0, 2},
{1, 2, 3}
},
InterpolationOrder -> {1, 1}
][0, 0]

returns 0, as expected, and

Interpolation[
{
{1, 2, 3},
{0, 0, 0},
{0, 2, 1},
{1, 0, 2}
},
InterpolationOrder -> {1, 1}
][0, 0]

returns 0, which is also correct.

Note that the format of the arguments to Interpolation was modified between
versions 5 and 6. Version 6 still accepts the version 5 notation in this
case. Using the version 5 notation in version 6 does not change the
incorrect behaviour described above.