Sending, receiving, and organizing email in Outlook.com
Did the error message specifically say that the IP was blocked?
If so, the domain host's response is correct. They cannot self block it. Microsoft has to unblock it. However, Microsoft will not simply unblock it because it was requested, because if the IP is bad, and action is not taken by the service provider to improve the IP reputation score, Microsoft will not just unblock it.
If you are domain owner, you can also try to request it. https://sender.office.com/ However, since you are not the server owner, you will not have access to do anything to improve the IP reputation.
Do you know what the IP is? If so, you can use free tools like MxToolBox to see if it might be also blocked by third party IP monitoring group. In that case, requesting from Microsoft will not help, as you need to request from them first.