Proposed resolution:

1. Change [alg.search] p.2 as indicated:

   template<class ForwardIterator1, class ForwardIterator2>
     ForwardIterator1
       search(ForwardIterator1 first1, ForwardIterator1 last1,
              ForwardIterator2 first2, ForwardIterator2 last2);
   
   template<class ForwardIterator1, class ForwardIterator2,
               class BinaryPredicate>
     ForwardIterator1
       search(ForwardIterator1 first1, ForwardIterator1 last1,
              ForwardIterator2 first2, ForwardIterator2 last2,
              BinaryPredicate pred);
   

   1 - [...]

   2 - Returns: The first iterator i in the range [first1,last1 - (last2-first2)) such that for any nonnegative integer n less than last2 - first2 the following corresponding conditions hold: *(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false. Returns first1 if [first2,last2) is empty or, otherwise returns last1 if no such iterator is found.

[ Adopted at 2010-11 Batavia ]

[ Post-Rapperswil ]

It was verified that none of the remaining possibly affected algorithms does have any similar problems and a concrete P/R was added that used a similar style as has been applied to the other cases.

Moved to Tentatively Ready after 5 positive votes on c++std-lib.

LWG 1205 (currently in WP) clarified the return value of several algorithms when dealing with empty ranges. In particular it recommended for [alg.search]:

template<class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1
    search(ForwardIterator1 first1, ForwardIterator1 last1,
           ForwardIterator2 first2, ForwardIterator2 last2);

template<class ForwardIterator1, class ForwardIterator2,
         class BinaryPredicate>
  ForwardIterator1
    search(ForwardIterator1 first1, ForwardIterator1 last1,
           ForwardIterator2 first2, ForwardIterator2 last2,
           BinaryPredicate pred);

1 Effects: ...

2 Returns: ... Returns last1 if no such iterator is found.

3 Remarks: Returns first1 if [first2,last2) is empty.

Unfortunately this got translated to an incorrect specification for what gets returned when no such iterator is found (N3092):

template<class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1
    search(ForwardIterator1 first1, ForwardIterator1 last1,
           ForwardIterator2 first2, ForwardIterator2 last2);

template<class ForwardIterator1, class ForwardIterator2,
         class BinaryPredicate>
  ForwardIterator1
    search(ForwardIterator1 first1, ForwardIterator1 last1,
           ForwardIterator2 first2, ForwardIterator2 last2,
           BinaryPredicate pred);

1 Effects: ...

2 Returns: ... Returns first1 if [first2,last2) is empty or if no such iterator is found.

LWG 1205 is correct and N3092 is not equivalent nor correct.

I have not reviewed the other 10 recommendations of 1205.