There is another issue that we hit a few months ago which might be related/unrelated. But the total time for Microsoft to lookup your DKIM record and get an answer can't be longer than 500ms or your DKIM fails, their answer is to use faster DNS servers. You'd think 500ms is heaps of time, but if you it include the time to do the NS lookups to see what server to talk to, etc. We were having issue where sending to hotmail/msn from the same account to the same hotmail account would bounce 50% of the time.. It depended on which MS server accepted the incoming SMTP.