It is impossible to create a three dimensional color space in which Euclidean distance corresponds directly to perceived color difference. There are dozens of papers on this topic, for anyone who wants some fun evening reading.
Yes, absolutely, which (I'm assuming) is why CIE2K difference is not-quite-euclidean. My opinion is the we still need to find a better difference metric, rather than improving the color space.
On that front, it's amazing to see how much of an effect "switching color spaces" can have on many algorithms.
