Proposed resolution:

This wording is relative to N4842.

1. Modify [algorithm.syn] as indicated:

   […]
   // [alg.three.way], three-way comparison algorithms
   template<class InputIterator1, class InputIterator2, class Cmp>
     constexpr auto
       lexicographical_compare_three_way(InputIterator1 b1, InputIterator1 e1,
                                         InputIterator2 b2, InputIterator2 e2,
                                         Cmp comp)
         -> common_comparison_category_t<decltype(comp(*b1, *b2)), strong_ordering>;
   template<class InputIterator1, class InputIterator2>
     constexpr auto
       lexicographical_compare_three_way(InputIterator1 b1, InputIterator1 e1,
                                         InputIterator2 b2, InputIterator2 e2);
   […]
   

2. Modify [alg.three.way] as indicated:

   template<class InputIterator1, class InputIterator2, class Cmp>
     constexpr auto
       lexicographical_compare_three_way(InputIterator1 b1, InputIterator1 e1,
                                         InputIterator2 b2, InputIterator2 e2,
                                         Cmp comp)
         -> common_comparison_category_t<decltype(comp(*b1, *b2)), strong_ordering>;
   

   -1- Mandates: decltype(comp(*b1, *b2)) is a comparison category type.

   […]

[ 2019-12-12 Issue Prioritization ]

Status to Tentatively Ready and priority to 0 after seven positive votes on the reflector.

The current return type is:

common_comparison_category_t<decltype(comp(*b1, *b2)), strong_ordering>

Finding the common category with strong_ordering doesn't do anything. The common category of X and strong_ordering is always X, so we can simplify it to:

common_comparison_category_t<decltype(comp(*b1, *b2))>

This can further be simplified, because the common category of any comparison category type is just that type. If it's not a comparison category then the result would be void, but the function would be ill-formed in that case anyway, as we have:

Mandates: decltype(comp(*b1, *b2)) is a comparison category type.

So the only effect of the complicated return type seems to be to cause the return type to be deduced as void for specializations of the function template that are ill-formed if called. That doesn't seem useful.