I have recently found that many organizations are unaware that they can take action on their own when it comes to blocked IPs and banned senders in Office 365. For both of these cases, a web based portal exists that can be used to remedy the problem, eliminating the need to create a support case with Microsoft.
I have an IP that is currently blocked by Office 365
An organization that is trying to send mail to an Office 365 recipient will receive a response similar to the following if their sending IP is on the Office 365 block list.
550 5.7.606-649 Access denied, banned sending IP [IP address]; To request removal from this list please visit https://sender.office.com/ and follow the directions. For more information please go to http://go.microsoft.com/fwlink/?LinkID=526653.
To request delisting, anyone (even non-Office 365 customers) can visit https://sender.office.com/.
More information can be found on the Use the delist portal to remove yourself from the Office 365 blocked senders list TechNet page.
I have an end user that is on the Office 365 banned senders list
A user that sends a large amount of email from Office 365 that is classified as spam by the service will be blocked from sending messages. This typically happens when an Exchange Online account has become compromised. A user in this state will receive an NDR (Non-Delivery Report) when they attempt to send an email message.
An Office 365 tenant administrator can lift the outbound ban for their users from the Action Center which is located under Protection in the Exchange Online Admin Center.
Just search for the blocked account and click Unblock Account. Note that there is a limit to the number of times an unblock can be performed in the tenant in a specific time frame. If this limit is reached, then an error will be thrown and a support case will need to be opened.
More information on this can be found on the Removing a user, domain, or IP address from a block list after sending spam email TechNet page.
Wrapping things up
If you find yourself in one of the above two scenarios, I would highly recommend first visiting the appropriate web portal. This will often lead to the quickest resolution. For any problems with the procedures outlined on TechNet, or if you would just like to chat with a friendly individual, you can of course open a ticket with Microsoft support.