We analyze a system in which in each time slot one customer and one server arrive at the system according to a random process. Compatibilities between customers and servers are determined by a bipartite graph. An incoming customer (resp. server), if it finds a compatible server (resp. customer), they are matched and both leave the system. Otherwise, they are stored in a queue. We investigate the impact on the expected value of the unmatched customers and servers when we remove an edge from the compatibility graph. For a quasicomplete graph and a large family of matching policies, we provide necessary and sufficient conditions on the probability distribution of the arrivals such that a performance paradox occurs, i.e., such that removing an edge of the compatibility graph improves the performance of the system. This phenomenon can be seen as an analog of the Braess paradox in bipartite matching models.