First is what you might call the combinatorial argument. If it's not illegal to release the information the blackmailer threatens to release, and it's not illegal to agree to do something for someone in exchange for a favor, then why should it be illegal for them to do it at the same time? In general, if A and B are both legal, why would it be illegal for A and B to occur together?
Second is the argument that it's a victimless crime, at least in the most strict sense of victimhood. People might be harmed by blackmail, and the harm is indeed sometimes worth making illegal, but blackmail in principle need not violate anyone's rights. Are my rights violated if someone tells an embarassing story about me? Are my rights violated if someone reveals some embarassing information about me? So I'm not a victim in that sense, and that's the sense that's required for making something illegal.
Chris Lutz, one of Joe's commenters, pointed out one problem with the more general combinatorial argument. There are plenty of counterexamples to the claim that if A and B are legal A and B together should be legal. Chris mentioned drunk driving, but it's extremely easy to come up with some where A and B are not independent actions by one person but involve more complex relations between people, which is what happens with the blackmail case. It's perfectly legal for me to sign a contract with someone that says they'll provide some service. It's also legal for them not to provide that service. It's not legal for them not to provide that service if I've signed a contract with them.
Another example would be consent and sex. It's perfectly legal for someone to deny consent to have sex. It's also perfectly legal for someone to have sex with that person. What shouldn't be legal is forced sex, i.e. sex with that person given that there's no consent. The blackmail case is just like this. The combination of the two factors is exactly what's wrong. It's not that either action is intrinsically wrong, but an action that's no intrinsically wrong can easily be wrong in the presence of certain factors that are not themselves intrinsically wrong.
Josh's response to the second argument seems right to me, but I'm not sure he goes far enough. He says that such crimes aren't really victimless, because these situations do violate rights. If I blackmail someone to get them to do something they wouldn't otherwise do, it's coercion. It's forced labor, something libertarians should be against. It's true that the force isn't physical force, but does that make a difference?
I don't think either of those responses goes far enough, though. The most obvious thing to me about this issue is what's long seemed to me to be the biggest problem in libertarianism to begin with. The idea is supposed to be that people should be free to do what they want to do as long as it doesn't harm anyone, but I can't figure out what that's supposed to mean. What does it mean to be free? It's not some metaphysical kind of freedom, because you're not free if you're held at gunpoint, and technically speaking you are metaphysically free at gunpoint. You do have the ability not to do what you're being told to do. You're just taking an incredibly huge risk of being killed. The same is true of blackmail, except that the risk may not be as physically harmful. In both cases, you have metaphysical freedom.
What you don't have is freedom from factors that might influence you. Of course, we never have that. All sorts of things influence us. I'm influenced to do certain things because people in my life expect things of me, sometimes justifiably so and sometimes not. If we can distinguish between legitimate and illegitimate expectations that may influence what we do, maybe that will help with figuring out what we should restrict legally. It doesn't take much further thinking to realize that even this won't do. There shouldn't be anything illegal about someone's having unfair expactations of me. Maybe it's immoral, but it shouldn't be illegal on any political theory, never mind on a libertarian one.
So what kinds of factors are supposed to be the bad kinds, the ones that we'll call coercive of some sort of use of force (whether physical or not) and which ones are just influences that are bad or good but shouldn't be restricted? That's what I'm not sure about. Socialists argue that we should restrict economic factors that we could help reduce by having a more equal society. I don't go that far, but in principle those factors seem to me to reduce freedom in exactly the way libertarians think we should be free. If my circumstances are such that I can't advance in terms of income, prestige, and opportunities for worldly success, then am I free to do what libertarians place the highest value on? The very height of libertarian success seems by its very nature to limit those who have started off at a lower point and haven't been as able to get the same opportunities as others. True libertarians think it violates the freedom of those who have opportunities to restrict them to provide those opportunities for others. Yet doing so is automatically restricting those others.
This is a real conflict in libertarian political thought, because it seems that anyone's freedom will almost certainly end up restricting someone else's. So when you try to figure out which freedoms you're going to restrict, you have to decide it based on some factor other than the pure value of freedom, because freedom is what's creating the conflict. We need a choice between freedoms, in particular between the freedom of one person and the freedom of another. Libertarians argue against slavery on the grounds that it's an uncontroversial case of one person's freedom restricting another's, but isn't the same sort of thing going on in all kinds of other social relationships?
Absolute ownership of a person is contrary to the central libertarian ideal, but so is a lesser degree of ownership over a person, e.g. ownership of whatever a person might produce but not of a person's body. Using influence over someone's freedom as a social superior to coerce sex out of a threat of job loss restricts someone's freedom, but so do the tricks many wives play with their husbands to coerce good behavior with sex as a reward. I think the latter is immoral, but should it be illegal in the way coerced sex under threat of being fired should be illegal? What's the basis if it's just freedom and lack of freedom that makes the difference? There isn't an easy answer to this kind of question, and I think that's the reason why it's harder for libertarians to deal with questions involving lesser degrees of coercion. Freedom admits of degrees, and one person's freedom can easily conflict with another's. It's hard to make an absolute of something that can admit of degrees, and when you add in the factor that almost any increase in someone's freedom will lead to decreasing someone else's, and it's the decreasing of someone else's freedom that libertarians are so opposed to. So the thing libertarians value most frequently decreases what libertarians value most.