At an even more basic level than what you described here, I recently improved my delivery rate by adding a name to the transactional emails that we send (from:

At an even more basic level than what you described here, I recently improved my delivery rate by adding a name to the transactional emails that we send (from: 'My Name <admin@foo.com>') where previously we didn’t have a name. As well as cleaning up subject lines - where previously we included some abbreviations. Providers like mac.com were previously soft bouncing some emails, and now they seem to accepting them. Hotmail/yahoo/aol all still seem to shove our transactional emails into spam pretty often (judging purely on the amount of those users who fail to confirm their accounts).