I like the approach of Dota 2:
- (1) If you leave a game you cannot requeue for a few minutes, from memory it is ten minutes
- (2) If you leave too many games you get into a 'low priority' queue
This is similar to what Valki describes. (2) is not possible due to the limited userbase and the technical involvement, but (1) sounds reasonable.
As an example, for every game you leave early on you get ten minutes of waiting time. For every game you play that waiting time is reduced with one minute. The waiting time is only applied when you left your previous game. If you leave a lot of games then your waiting time increases significantly. But if you occasionally have to leave a game due to circumstances it will have little to no impact.
I'm not familiar with the implementation of the client / server. This would need to be implemented on the server with a client UI that describes what is going on.