No. I didn't miss the point. The user, writing standard-conforming code, would not get your random access iterators, because begin() and end() wouldn't provide them, and the range-based for loop wouldn't use them. OTOH, if the user used another means to get your random access iterators and chose to use them with std::find(), the code would be non-conforming, but might do exactly what the user wanted.
Okay - but the code I'm writing, in writing the non-conformant code, would be non-conformant, no? Anyway, we're splitting hairs at this point I guess :) A valid alternative would be to have functions separate to the iterator which alter the iterator state, but don't belong to the iterator as such. It's probably worth doing, but would make for fairly ugly code compared to standard operator-based functions.