I’m currently having this exact same issue, but I already have DKIM on, and have for at least a year. I went ahead and re-generated a new entry, but that hasn’t seemed to help at all. I am completely without ideas at this point. I looked at the logs in our Admin console and it looks like not every email to a MessageLabs customer gets blocked, just most of them.