We study a performance paradox in stochastic matching systems motivated by kidney exchange problem. Items of different classes wait until they are matched with compatible items, after which they depart immediately. Compatibility between classes is represented by a graph. One would expect that adding an edge to this compatibility graph reduces the expected total number of unmatched items in steady state. A performance paradox occurs when this number instead increases. Recent work has shown that such a paradox can arise under greedy matching policies, particularly in systems whose arrival rates lie close to the boundary of the stability region. We show that this type of performance paradox is more common than previously thought. It can also occur in matching systems with abandonment.