Reputation for your IP takes time. Some providers are smarter than others about how long you need to establish a reputation. Google seems quick if you follow the rules. Microsoft and AOL seem on the slower side, we give an IP a few weeks to "warm up" its reputation. And you need to be active about handling bounces, spam reports, etc. from day one.
Sending rate is also a huge signal for some providers (Microsoft) and seemingly not for others. In our experience, if you send more than one email per second per IP to Microsoft over a few hour period, that IP is almost guaranteed to get put in the penalty box for a few days. Stay under the limit and adhere to the other guidelines in that post and you're fine.
If you're going to be sending at higher volume, use different IPs for "transactional" mails -- signup, password reminders -- than for monthly mailings, etc. This way you protect the reputation of the IPs sending the stuff you really need to get through. (In all cases, you better be sending mail to registered, double-opt-in addresses, otherwise look in the mirror, you're a spammer.)
Also as another poster stated, sign up for the feedback loops. Some are a huge pain (Microsoft), some are very straighforward (Yahoo).
http://feedbackloop.yahoo.net/
http://postmaster.aol.com/fbl/fblinfo.html
http://postmaster.live.com/Services.aspx#JMRPP
http://feedback.comcast.net/