The following instructions explain how to remove an IP address from Microsofts Office 365's RBL.
It's important that you figure out why you were blocked to begin with so that you are not blocked again. Make sure your mail server has not been compromised and ensure that your email queue does not contain any spam. We've seen administrators correct a compromised script but forget to clear their mail queue!