Firstly, it would not solve this problem since Valleywag stories tend to get lots of upvotes. Indeed, it would encourage posting link-baiting stories, since they also tend to be karma-baiting stories.
Secondly, it would stop people from posting borderline, but valid stuff. I often don't post things I'm unsure people will like, but many times posts that seem borderline to me end up getting loads of upvotes. With a karma cost for posting, people would simply not post these kinds of stories.
A karma cost for posting is a recipie for encouraging lowest-common-denominator stuff.
In that case, the "let's ban valleywag" approach is even more wrong. The problem of "garbage gets voted up" is one which ought to be solved long before the problem of "people submit garbage".
A while ago I suggested a 'name and shame' approach, where 'bozo' votes, if there are enough of them, reveal who voted for a story.
As an aside, I wonder if each of article submissions, comments, and voting could be thought to respectively show that a person is interesting, intelligent, and has good judgment?
It would be a weird scenario indeed if vote-buyers were only able to pay out for stories that did not get a positive score.
Vote-buyers could still gain some long-term information that would enable payment, such as the reliability of a given paid-voter over time (by checking the stories that didn't make it), but that same information would be available to the news.yc admin(s), who could then just ban the offending accounts (even if they weren't suspected of vote-selling--just for consistently supporting crappy stories!).
In other words, if you vote up a story and then change your vote a day later, the vote has already contributed to putting the article on the front page on that first day, and so the "damage" has already be done.
I haven't seen so many forums that use tagging where it actually works in a very useful way.
I've said this before, and I'll say it again: Users who post garbage stories should be more accountable. Make posting a story cost a few points of karma, so that people who repeatedly post stories which don't get voted up end up without any karma.
The specific problem of linkbait titles might also be helped by allowing users to "un-vote" a link which they previously voted up.