In my experience, setting up a SPF record will basically solve the problem for Hotmail and Gmail. However, I have heard Gmail uses a reputation-based system, so basically you are innocent until proven guilty... so make sure your users actually want to receive additional emails. From what I read, it only takes a few people marking your Email as spam to get blacklisted. I haven't had this problem yet though.

I recommend you to check out the link I listed in my original post -- there are some great tips in there for getting through spam filters.