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.

2.
Currently you can setup a grid as

``
{"metric": ["minkowski"], "p": [1, 2, 3]} 
`` 

or 

``
{"metric": ["minkowski"],  "metric_kwds": [{"p": p} for p in range(1, 4)]}
``

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``).

3.
OK, let's not remove ``p``. But if ``metric_kwds['p']`` is set, then ``p`` from ``__init__`` is ignored. Agreed?