Seems to me putting a karma requirement on posting, and requiring X up-votes before it gets to the main job page would solve that problem.

And create a new problem of more people trying to game the karma system. I think it's best to leave jobs (no pun intended) out of this place.

Does a site do this? This sounds like a great approach to that sector.

I'm not entirely sure if this is the right approach, but a job site that works as well as job postings on HN is definitely in demand

We could make it like doostang, so you need to have somebody invite you in order to make an account

The "is anyone looking" approach doesn't work well here. Unlike regular forum threads, HN posts will disappear from the front page very quickly even if people are still replying to it.

Maybe someone can solve that hard problem while they're at it?

Leverage whatever's keeping HN relatively spam-free.