I wouldn't cache the hash code in this class. If the pair contains a mutable object, then the hash code of the mutable could change during the lifetime of the Pair, causing the Pair hash code to break. Just calculate the hash code on demand.
I'd also avoid MatchedPair if possible. I'd like to see Pair be final and immutable (dependent on contained data).
I don't especially see the value of the iterator per se, but having a way to convert a Pair to a list might be useful. That method could have an option to expand any pairs it finds (and this could be built on an iterator internally, rather than up front extraction...)
In general though, a [lang] Pair needs to be simple and non-religious