After much messing around and several calls to my vps provider some time ago I established that the graylisting included with plesk panel does something funny with Microsoft hosted email. Things like outlook.com, hotmail, live.com, anything from BT (which is all Microsoft hosted).
Having just had a new shiny pleaks v11 server commissioned and have hit the same problem. It's virtually unusable without some graylisting but the built in one has this massive (in my opinion) flaw.
Whilst trying to find the solution again (didn't make a note last time...) I came across this article from Parallels.
http://kb.parallels.com/en/114739
It explains that the issue is because Microsoft dared to use the word "pool" in the FQDN of their outbound mail server pool. Now, it seems to me that if you have a pool of servers using the same name that using the word pool is a fairly reasonable thing to do when you describe it. Maybe they should increase the size of the pool and call it a lake, mear or water. Alternatively they could reduce the pool and make it a puddle.
Either way, to resolve the issue you need to turn off the greylisting, remove the word pool from the list of things that it looks for or whitelist the microsoft servers. The following command should do the latter for you, not sure if maybe just *.microsoft.com would be safer but I'll see how this does first.
/usr/local/psa/bin/grey_listing --update-server -domains-whitelist "add:*messaging.microsoft.com"
Please note that I have just stolen that line from the above referenced article, I didn't work it out my self.
I guess you could add this in via the web interface but that's just not hard core enough for me.
