It is actually possible to address this issue in a rather simple way, although it was not so evident what to look for.
The Game Center Programming guide actually states that "You can create distinct games (with different bundle identifiers) and still allow them to play against each other."
So you have to click "View Details" of one of your apps. There, if you have enabled Game Center for your app, edit "Multiplayer Commpatibility" and add the other app to the list. Now you can play matches across different apps.