That is your last option buddy. The IMEI is your phones serial number and is unique to that phone. The only way you can fix it is by replacing it with the IMEI of another iPhone but that IMEI has to be clean also. Which would only come from getting another phone or buying one new.
I had my IMEI blacklisted for hacking Apple music. They got me because it crashed on my wife and she hit the "send crash diagnostic to developers" button lol. I had gotten busted once before when I made an in app purchase on an app I cracked. There are lots of ways to get blacklisted.