For examples of forced conversions inserted to deal with this issue, search for "pred" in http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/include/bits/stl_algo.h?vi...
Interesting. It's terrifying that somebody should have to do that.
Looking at N3351, I wonder if you implemented these algorithms and threw strict archetypes at the implementations. It looks very much like you would need similar contortions.
We did (omitting a handful), with constraints mostly matching what appeared in n3551, but the archetype framework wasn't in place until some time later. If I remember correctly, we assumed that a conversion requirement on the result of an operation, would actually convert (if necessary). You couldn't, for example, return tribool from == and expect the compiler to pick up overloads for &&, ||, and !. That would be a bad thing (unless your generic algorithm was parameterized over the underlying logic). I'm not sure if you can successfully guard against this using SFINAE-constraints. You'd need to write a ton of explicit conversions (like above). Or language support, of course.