Конечно реальный вопрос: Почему такое произвольное ограничение?
Я бы посчитал совершенно нормальным иметь тот же тип, что и ключ и значение, поэтому, вместо обеспечения неоднозначной перегрузки оператора, возможно, вы могли бы просто предоставить два разных метода?
ValueType const& by_key(KeyType const&) const;
KeyType const& by_value(ValueType const&) const;
и покончим с этим.
РЕДАКТИРОВАТЬ : После замечания Георгия Фрицше:)
Помните, что одним из первостепенных правил перегрузки является то, что все перегрузки должны иметь одинаковое основное значение.