other than flat out not allowing a player to re-enter the same instanced they were kicked from, there isn't much they can do.

the whole can't be paired with blacklisted players gets complicated and makes ques very long, seeing how once you start adding in everyones blacklist the number of players that could be paired is greatly decreased.

a player kicked shouldn't get a penalty as there are plenty of vote kick abuses and someone getting a penalty because of trolls is not the way to go.

the best i can say (even though its not the best solution) just kick the player if said player returns kick again and proceed to leave before anyone joins so you may avoid the 30 minute penalty.
but like i said its not the best but its a ok temp till something is done (if anything at all)