This is fairly tough situation to deal with, and UCEPROTECT touches on it specifically:
https://www.uceprotect.net/en/index.php?m=7&s=0
That sounds like the situation you're in, right?
I was able to rectify a similar situation for a client by asking the host to communicate directly with the RBL. I explained everything that they had to do, and surprisingly, they had it resolved in a reasonable amount of time. I am not sure if they used the contact form, but that's a dangerous game to play. Being the host itself though, that gives you a lot more credibility than a client.
For UCEPROTECT, they've laid out the steps you take, and yeah, they're pretty strict. Other RBLs are easier to work with, and I've had good luck just emailing them and explaining the situation on behalf of my clients without the host needing to be part of the conversation. YMMV.
This is what I saw with UCEPROTECT:
https://www.uceprotect.net/en/index.php?m=8&s=0
Leads you to:
https://www.uceprotect.net/en/index.php?m=7&s=7
or
https://www.uceprotect.net/en/index.php?m=7&s=8
This gets you here:
https://www.uceprotect.net/en/rblcheck.php
Please note this page:
https://www.uceprotect.net/en/index.php?m=4&s=0
The rblcheck page should provide context on how to get unflagged, but, again, by association, this is a huge problem because you're sharing the entire IP block with others and these RBLs do not care about your personal situation. It's important whether you're in 2 or 3, or both. You have to read every line they've written because they expect that.
When it came to mailers for my clients, and this happened, I really had no choice but to reissue a new dedicated IP address. Since then, I've had good luck by combining an existing MTA who is "okay" with adult content, and self-hosting software that can use that MTA to send emails out. Luckily, even on shared IP pools, this hasn't been an issue.