Yeah some sort of system that ejects people if they can't connect after X amount of time seems like it would help. The situation you outline above has happened to me multiple times and then it usually ends with the search stopping and me getting an error message.
If I've pushed the button to play Pantheon, that's what it should do. It should not stop until I get into a game successfully or the search takes too long (n time) at which point it should come back with a prompt, "Having trouble finding a game, would you like to continue searching?".
I can stress enough how bad it is to the end user to have it stop searching and just present an error message -- this should never happen.
(Error messages posted to log files fine, a window that continually notifies the current status saying things like, "Found X number of other players but could not connect to all players, attempting to find more players" would be ideal).
-Jara
PS: I suspect this will be needed in addition to the proxy server stuff you are working on. No case can be 100% successful and the code needs to be ready to handle that so that one bad apple does not shut down everyone elses play experiance.
PPS: I'd also go so far to suggest that once someone hits the search button, controls should be removed from the player to prevent impatient players from pulling out before giving the search long enough time. Granted this only works if you have a fail safe that after N amount of time of searching it comes back and ask the player, "Would you like to keep searching?" at which point that is when the user can choose to exit the search or continue.