We recently setup a customer's Exchange environment (9/23/2013) and their public IP was immediately placed Microsoft's block list.  I validated via mx toolbox that it is not an open relay, ptr record is in place etc., The IP is not on any Blacklists for SPAM.  I have been trying to get this IP removed from Microsoft's Block list since Saturday evening and been told that it takes up to 48 hours which this time has come and gone.  At this point I have submitted multiple tickets to have this removed, submitted a message to delist@messaging.microsoft.com and I am still not removed.  This is just load "####"  why must you work so hard to get something removed that should have never been blocked in the first place?  My frustration grows as Microsoft continues to not resolve this problem which impacts productivity at a customers site! The only people that they cannot send email to is Office 365 based customers if anyone has any ideas to assist I would greatly appreciate it.  Below is the message I get when sending to Office 365 users.

BN1AFFO11FD022.mail.protection.outlook.com gave this error:
Service
unavailable; Client host [x.x.x.x] blocked using Blocklist 1; To request
removal from this list please forward this message to
delist@messaging.microsoft.com