After about a week of wrestling with this issue, we've now resolved all of them except for Microsoft blocking my emails. They've unblocked me multiple times (3), only to reblock me couple days after.
The error message returned by them is:
host mx1.hotmail.com [126.96.36.199]: 550 OU-002 (SNT004-MC4F31) Unfortunately, messages from 188.8.131.52 weren't sent. Please contact your Internet service provider since part of their network is on our block list. You can also refer your provider to http://mail.live.com/mail/troubleshooting.aspx#errors.
Looking that error up on their site shows:
Mail rejected by Outlook.com for policy reasons. Reasons for rejection may be related to content with spam-like characteristics or IP/domain reputation. If you are not an email/network admin please contact your Email/Internet Service Provider for help.
Basically, the issue seems to still revolve around my new server's IPs having a bad reputation because of it's previous owners. What can I do about this? Is it some other problem?