> 1.
> At the moment I can't point you to a famous paper or something on this topic. But, for example, it can be useful for searching of feature weights using wminkowski metric. In order to find relative importance of features in distance computation. As far as I know it's called "metric learning" in general.
> 
> Another situation is when a user implemented his own distance function which accepts some parameter. Without explicit metric_kwds he won't be able to cross validate his estimator. It's very disappointing.

I wasn't clear. Is there an example in the documentation that illustrates the use of custom metrics? While reviewing, I quickly searched for an example and haven't found one.

>Could you explain how it can possibly accept "metric_kwds__p"? As far as I understand such names are used for set_params on estimators that contains other estimators (like Pipeline).

Indeed. Without a get_params and set_params, you can't.



> 3.
> OK, let's not remove p. But if metric_kwds['p'] is set, then p from __init__ is ignored. Agreed?

This would require proper documentation.

On the other hand, this might be time to clean everything. 
( Special cases aren't special enough to break the rules.)
Sorry for puzzling. Ping @jakevdp, @ogrisel.