It looks like the internet is already trying to solve my problems. Notchup.com (article) is a beta job posting board where you can set a price that companies must pay to interview you. The suggested prices seem to run from $100-$600 or so, although you can set anything you want. This strikes me as a step in the right direction: interviewing takes a nontrivial amount of time, so if you're good enough, companies should pay you for the privilege. It also shows that they're serious about you and aren't going to demand a whole bunch of information, they contact you six months later to let you know the position has been reorged out of of existence. And it's certainly cheaper for them than paying $10k to a headhunter to call you at work.
There are restrictions, of course. They have to approve you before they'll let employers see your resume, with an eye towards graduates of prestigious schools, workers at prestigious companies (although they allow for both fortune 500s and startups), and "in-demand skills" , which I suspect means they'll lower the bar for workers in fields suffering from a labor shortage. They claim to have an algorithm to detect "serial interviewers" who are just in it for the cash, but I don't know how they'd distinguish that from "people who really like their current job." There's a reputation system involved, so my guess is that companies can rate people who they think deliberately spiked the interview. But that's never going to be perfect, and companies will be very wary of paying you to interview for a job you'll never take. I think the next step is for the potential employer to donate to the interviewees favorite charity, so he or she receives no direct financial benefit, yet the company has proven that they are serious.
(hat tip: my money blog)