Delivery is delayed errors, seems specific to Office 365 recipients

To fix this get a new IP address for your outbound mail server ASAP. Remember to also realign reverse dns for the IP address. Also continue on with the blacklist removals. If you cannot get an external IP consider a 3rd party mail filtering service or a gateway.

As a follow up, don't send mail directly from exchange out to the internet. If possibly put in a secondary mail gateway that will allow you to better manage your outbound emails. You can set this up very easily if you have a bit of linux experience, and also you can keep a good record of who is using your email server for what. You could also do this by enabling SMTP logging on the SMTP virtual server in exchange, but I find even this log to be a bit of a pain to get accurate measurements for.

If you cannot use a gateway, even if just as a temporary measure use an external provider such as postini or message labs. http://www.google.com/postini/index.html

I opened a case with Microsoft. They connected to my computer and had me 2 hours going back and forth doing tests (they were very polite, and tried to help).

Their suggestions are the same above. That didn't help. However, they thought that my profile having too many rules (+100) might have something to do.

Offline I cleaned up my rules, deleting a lot of rules that I had disabled (~20 rules). That fixed the issue.

It seems that some rule was corrupted, or my total rules count didn't allow Exchange to add the rule for the automatic reply. In any case, my situation is resolved.