No, it is not right that an "object" is always an instance of a class. Just for example, the standard for C (which doesn't have classes at all) defines an object as (§3.14/1): "region of data storage in the execution environment, the contents of which can represent values."
Now, it is true that using "object" to refer to an instance of a class is quite common. In some languages (e.g., Smalltalk) all objects are instances of classes. In others (e.g., C++) the term is somewhat ambiguous, because there is a C-like use of the term and a Smalltalk-like use of the term, so it's not necessarily clear whether "object" is being used to refer specifically to an instance of a class, or just to some region of data storage in the execution environment, which may be an instance of some primitive type rather than a class, or may be (for example) some dynamic storage that hasn't been initialized, so it's not really an instance of any type.
As far as "object instance" making sense, I can see one situation where it could. Going back to Smalltalk: everything in Smalltalk is an instance of a class -- even a class is an instance of a class (called the metaclass). In a case like this, I can see where it could (sort of) make sense to talk about an "object instance", when you were specifically talking about an instance of a class as opposed to the class of the class.
In fairness, however, that usage is undoubtedly quite rare (at most). The vast majority of the time, "object instance" is probably just sloppy wording.