というわけで，ここまで長々訳の分からないことを書いておきながら，結論は至ってシンプルです．自前のfor文回すのが一番楽ですが，ここはあえて既存のアルゴリズムでやってみました．
templateinline bool is_sorted(ForwardIterator first, ForwardIterator last, StrictWeakOrder pred) { ForwardIterator it(first); return equal(++first, last, it, std::not2(pred)); }
上のコードはcomp.lang.c++で書かれていたものを若干変更したものです．predがadaptableであることを要求しているのが唯一残念なところです．equalの使い方が本来期待されている使い方と異なっていますが，規格書読む限りはこれも正しい使い方であると思われます．ただし2つのiterator範囲がoverlapするので，equalが本来要求しているInputIteratorではなく，ForwardIteratorが必要になります．というかこのequalの使い方は結構( ・∀・)つ〃∩ ヘェーヘェーヘェーな感じ．
1つだけ注意として，Strict Weak Orderの否定が何を意味するかですが，上の議論から「!(a < b)」は「a > b または a <> b」を表すことになります．そしてこのequalは結局，隣接する要素a, b（要素の順序はこの順とする）において「a < b または a <> b が成り立つ」ということを確認しています．これがsortの事後条件をきちんと確認していることは上の議論のとおりです．
最後に余計ながら，自分が考えたコードを示しておきます．
templateinline bool is_sorted(ForwardIterator first, ForwardIterator last, StrictWeakOrder pred) { return std::adjacent_find( first, last, boost::lambda::bind (pred, boost::lambda::_2, boost::lambda::_1)) == last; }
lambda::bind持ち出していますが，やっていることは非常に単純です．ちなみにこのコードはequalによるis_sortedのコードとまったく等価です（一見しただけでは分かりにくいですが）．
後，他にiteratorを逆回しにしてアルゴリズムに突っ込むコードもありましたが，iteratorに対する要求がForwardからBidirectionalになってしまうので避けました．
