We got a /24 at our data center and the reputation was, unfortunately, poor. I went through all of the public reputation lists and asked to be removed. It took about three months of incremental effort, but the reputation for the entire /24 is clean now.
This is with a "real" mail server, and not mailu.io, but the idea is the same.
I just went to my cloud provider of my choosing and started to add floating IPs. After a few tries I got a good one. I went through the unblocking process once, and I decided not to do it again. Especially Microsoft gave me a hard time, they started to request documents and then let me wait a few weeks until they replied: we don’t unblock, and we don’t tell you why.
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.
This is with a "real" mail server, and not mailu.io, but the idea is the same.