Tangotiger has an idea: replace the MLB draft with an auction. Players could list teams they abjectly refuse to join, and part of the final bid will go to those teams, thereby making it costly for a player to refuse to negotiate with a particular team (or set of teams).
I really like this idea, but I would make one modification: make this a second-price auction. In other words, whenever there are at least two teams which make bids, the final price is the second-highest bid. This is an efficient auction, in that you will end up with the players receiving their market value and the teams not tending to bid beyond that value.