Google marks seemingly perfect emails as spam
mxtoolbox has a pretty comprehensive blacklist checker. I know you already checked but this might be useful to others who come across this post as well.
Your best bet - as mentioned by caelyx - is to implement DomainKeys and be done with all this nonsense. Yahoo and Gmail both green light dkim signed email till they have reason to do otherwise (users tagging it spam). If this is at all business related it's a pretty obvious choice ROI wise. An hour or so of configuration and testing equals much fewer issues with spam filters.