I think a carefully targetted link exchange site would be pretty useful.
Webmasters exchange links indiscriminately. Well, they get kicked out of the index eventually and the links did no good for their site, traffic wise anyway.
Boohoo. They were probably were competing with us anyway. :)
Webmasters exchange links responsibly. I post a message / advert saying i want to exchange links with a widget related site. I get widget related links.
This is no different than emailing these webmasters individually.
I would say a carefully run service such as this would be useful.
But, as Heini noted, there are a lot of problems with it.
Even if you can keep your site clean from any spammy techniques, it will still be a hunting ground for spammers outwith your control. No one knows what kind of attitude the search engines would take to this. Not likely to be a good one though! :)
Also, I wouldnt pay for such a service at all - im cheap and dont pay for what i can do for free! ;)