How to get delisted from Microsoft's block list for Office365 / Exchange online. 

Here are some online resources you can use to test your email server to ensure you are not blacklisted or have DNS configuration issues:

http://mxtoolbox.com/diagnostic.aspx 
https://www.ultratools.com/tools/spamDBLookup 
https://www.ultratools.com/tools/emailTest 
http://www.dnsstuff.com/tools

1.

Send a delisting request to Microsoft.

Forward the undeliverable notice you get from Microsoft to the indicated address. In my case it was delist@messaging.microsoft.com. Do this from the domain that can't send email to the Microsoft hosted domain.

Example:

From: System Administrator 
To:YourName@YourDoamin.com 
Subject:Undeliverable: Bla Bla Bla

Your message did not reach some or all of the intended recipients.

Subject: Bla Bla Bla 
Sent: 2/4/2014 10:28

The following recipient(s) cannot be reached:

Mr. Bill on 2/4/2014 10:28 
You do not have permission to send to this recipient. For assistance, contact your system administrator. 
<mail.xxxxxxxxxx.com #5.7.1 smtp;550 5.7.1 Service unavailable; Client host [XXX.XXX.XX.XX] blocked using Blocklist 1, mail from IP banned; To request removal from this list please forward this message to delist@messaging.microsoft.com and include your ip address XXX.XXX.XX.XX .>
2.

Ensure you receive a reply

You should soon get a reply back from Microsoft...

From:Microsoft Customer Support [BlaBlaBla@css.one.microsoft.com] 
To:you@yourdomain.com 
Subject: RE: SRXxxxxxxxxxxxID - XXX.XXX.XX.XX

Hello , 
Thank you for your delisting request SRXIxxxxxxxxxxD. Your ticket was received on (Feb 04 2014 03:23 PM UTC) and will be responded to within 24 hours. 
Our team will investigate the address that you have requested to be removed from our blocklist. If for any reason we are not able to remove your address, one of our technical support representatives will respond to you with additional information. 
Regards, 
Technical Support
3.

Call Microsoft @ 800-865-9408

You can wait the indicated 24 hours as I did. (No one contacted or emailed me) Or you can wait a reasonable amount of time (whatever you can stand) and then call.... 800-865-9408 and give them the ticket number you were sent in the reply email you should have received in step 2. SRXIxxxxxxxxxxD

I had to make the call. I was sent to a tech who could not help me but said he would forward my ticket to another department for resolution. He said I would receive a response in about an hour.
4.

Look for the response email

Wait for the email. Mine came in about an hour or so...

From: Microsoft Customer Support [BlaBlaBla@css.one.microsoft.com] 
To:You@YourDomain.com 
Subject RE: SRXxxxxxxxxxxID - Delist XXX.XXX.XX.XX

Hello , 
Thank you for contacting Microsoft Online Services Technical Support. This email is in reference to ticket number XXXXXXXX which was opened in regards to your delisting request for XXX.XXX.XX.XX 
The IP address you submitted has been reviewed and removed from our block lists. Please note that there may be a 1-2 hour delay before this change propagates through our entire system.

We apologize for any inconvenience this may have caused you. As long as our spam filtering systems do not mark a majority of email from the IP address as spam-like, your messages will be allowed to flow as normal through our network. However, should we detect an increase in spam-like activity, the IP address may be re-added to our block list.

Should you have any further questions or concerns, please feel free to respond to this email.

Thank you again for contacting Microsoft Online Services technical support and giving us the opportunity to serve you. 
Sincerely, 
SAM I AM 
Microsoft Online Services Technical Support 
5.

Test the resolution.

Wait about an hour after the receipt of the resolution email and test again. All should be good.

Conclusion

It seems Microsoft is very slow about responding to these requests so a phone call may be your best bet but you need that ticket number.

-----------------------------------------------------------------------------------------------------


See the original article here:-

http://community.spiceworks.com/how_to/show/67285-getting-delisted-by-microsoft-delist-messaging-microsoft-com