Over on Spamtacular, Mickey Chandler answers the question, "Our last mailing had 30 complaints at AOL. Will signing with DKIM and SPF help with our reputation there?" As Mickey explains, it boils down to, no, not really, that's not what authentication does.
In short, auth don't fix that.
Authentication helps your delivery, sure. It helps ISPs better tell good mail from bad mail. Authenticated mail means there is a proven connection that the mail you're receiving really came from who it claims to be from. It's a stable identifier for ISPs to use to determine domain reputation. Meaning, authentication allows internet service providers to easily compile data on how well-loved your domain is (or isn't), and that helps to them to exclude phishing and spoofing from that equation.
It's a good thing, but it's not some magical thing. “If you authenticate your mail, it will suddenly stop getting complained about” is not a true statement.
And there are a couple of really important things at ISPs that help senders, things that are tied to authentication.
Authenticate with Sender ID when sending to Hotmail, and you'll receive a modest deliverability boost. Why? Because they chose to build it that way. I read a white paper from 2007 that suggested that perhaps authentication was perhaps 11% of the overall deliver/don't deliver equation at Hotmail. Meaning, if you generate tons of bounces and spam complaints, that'll still damage your deliverability. But, if you're mostly good about what you send and whom you send it to, that little bit of positive boost from authentication can really matter.
And then there's Yahoo's Complaint Feedback Loop. The thing that, when you hit the “Spam” button, results in a spam complaint report being sent back to the sender or the sender's service provider. This is very valuable to senders, and their service providers, because it allows you to build your own stats on reputation. It lets you know which mailings have the most complaints, so you can focus your remediation efforts appropriately.
You only get access to Yahoo's feedback loop if you authenticate your mail with DomainKeys or DKIM (DomainKeys Identified Mail). Does it have to be that way? Maybe not, but that's what Yahoo has chosen to do.
So, authentication itself doesn't magically improve your deliverability, but it is tied to some things that can and do have a positive impact on a sender's ability to deliver mail.
But it's not going to make the spam complaints stop. That's a whole other problem.