This is a problem of poor interface design for the container, not a problem with unsigned types. I would prefer something like this using an output parameter for the index:
bool IndexOf( const T& x, size_t& index ) const;
Then the usage of the method is:
if ( container.IndexOf( x, index ) )
… use index
In general I agree with "don't conflate error codes with values", but when it comes to array indices I'm not as convinced (I mean, even the C++ standard conflates valid iterators with errors).
The pattern above becomes cumbersome in the common case when you know IndexOf will succeed.