Proposed resolution:

p2 [map]: Above the declaration of class value_compare in the map synopsis, add:

template <class Key, class T, class Compare = less<Key>,
          class Allocator = allocator<pair<const Key, T> > >
class map {
public:
  // types:
  ...
  // exposition only.
  class value_compare
    : public binary_function<value_type,value_type,bool> {
    ...

p2 [multimap]: Above the declaration of class value_compare in the map synopsis, add:

template <class Key, class T, class Compare = less<Key>,
          class Allocator = allocator<pair<const Key, T> > >
class multimap {
public:
  // types:
  ...
  // exposition only.
  class value_compare
    : public binary_function<value_type,value_type,bool> {
    ...

[ 2010-01-31 Moved to Tentatively NAD after 5 positive votes on c++std-lib. Rationale added below. ]

The container class templates map and multimap both contain a nested type called value_compare, that is used to compare the value_type pair elements, an adaptor of the user-supplied comparison function-like object.

I believe these types are over-specified, as we require a distinct type for each template, even though the allocator plays no part in the comparator, and map and multimap value_compare classes could easily be shared. The benefits are similar to the SCARY iterator proposal (although on a much smaller scale!) but unlike SCARY, this is not a QoI issue today but actively prohibited.

If the value_compare classes were marked 'exposition only', a vendor would be free to experiment with implementations that do not produce so many template instantiations with negligible impact on conforming programs. (There is a minor risk that programs could no longer portably overload functions taking value_compare types. This scenario is extremely unlikely outside conformance suites.)

(Note that there are no similar problems for unordered maps, nor any of the set variants)