Trying to find help for 550 5.7.511 Access denied, banned sender

I run a mail server for many business clients of mine. Microsoft have blocked our IP address, so we cant send to Office365 email addresses. I get a bounce back saying:

host cr-studio.mail.protection.outlook.com[104.47.21.36]
said: 550 5.7.511 Access denied, banned sender[12.34.56.78]. To request
removal from this list please forward this message to delist [at] messaging.microsoft.com. For more information please go to
http://go.microsoft.com/fwlink/?LinkId=526653. AS(1410)
[LO2GBR01FT022.eop-gbr01.prod.protection.outlook.com] (in reply to RCPT TO
command)

(I have changed my server IP above)

So I emailed delist[at]messaging.microsoft.com but they said:

"I do not see anything offhand that would be preventing your mail from reaching our customers for the following IP : (12.34.56.78)"

And gave me various links to pages with different support channels. One of them was to login to admin.microsoft or something, but I cant do that as I dont have an account. 

One of them was contact Microsoft support and they said its not to do with them, contact Office365. 

So I filled in a form on sender.office365.com and they replied:

"The IP address in question is not currently blocked in our system. Please refer to the email message you received from Microsoft and follow the steps it suggests." - which I have done, with the first email above!

I also filled in the form for emailing Live, Hotmail, Outlook.com and got no reply but dont think its to do with them. 

So I am very confused at the moment with all the different support channels, various Microsoft support telling me they cant see a reason for the block and then doing no more about it. 

I have no idea what the correct channel is and how to fix this, does anyone know? Its a bit of a shambles Microsofts side of it to be honest.