Ask HN: Are email providers getting more strict with mail from your web app?

Lately, one of our web apps (Rails) has been receiving more bounce backs and delays when trying to send mail. Yahoo! mail seems to be the biggest problem. We've already lost a customer who was frustrated that they couldn't reset their password.

Has anyone else noticed email providers getting more strict with email from your app? I've set up SPF records and domainkeys. Still no love.