Forum Moderators: open
I don't know specifically about Korea, but I think that most countries have contract laws that are more or less similar to what I am familiar with from Germany. This legislation says that a clause in a contract between two parties is invalid, if its outcome depends on the actions of a third party that has not also signed the same contract.
In your case, your SEO contract purports that you can garantee placement on Yahoos site, while in reality the contractually uninvolved third party Yahoo is the only entity that has full control over that placement. You are therefore promising something to your clients that you have no power to deliver, other than by chance.
Based on the same principle, a client might also be tempted to establish a case of false advertizing if you should happen to miss your target.
Did Yahoo offer any explanation of their own?
Of course, just them saying so doesn't necessarily make it illegal, but chances are they do have a point. The other interesting question is, even in the case that your garantee was illegal as a contractual clause between you and your customers, whether Yahoo has any legal way to hassle you about it (other than by simply dropping your listings).