Is it possible that Microsoft distrusts your IP range? Some providers are known not to be very responsive to abuse reports. And then whole IP ranges get (soft) blacklisted, and individual IPs can’t be unblocked, without having a very strong case.