How do I add my stolen iPhone back to my Apple ID?

If you removed it from your devices list then the only way to get it back on the list is for you to sign in on the device itself.

Read this support article to learn what you can do if Find My iPhone or Find My iPad isn't enabled on your missing device --> If Find My iPhone or Find My iPad isn't enabled on your missing device - Apple Support

Use the Find My app to locate a missing device or item - Apple Support

"What happens if you activate Mark As Lost

Mark as Lost remotely locks your missing iPhone, iPad, iPod touch, or Mac with a passcode, keeping your information secure even if your device goes missing. You can also display a custom message with your phone number on the Lock screen, and keep track of your device's location.

Once Mark as Lost is activated, Apple Pay is disabled, if you have it set up on the device. A confirmation email is sent to the primary email address associated with your Apple ID. When you recover your device, you will need to unlock it with your passcode."

Blacklisting is something totally outside of Apple's purview. My understanding is if another company who uses the same service sees a device is blacklisted they will not offer carrier service on that device. I believe they use the IMEI which is something Apple does not use.

I can think of a way but that would also let the thief have complete use of the device since it would then be like new. --> https://al-support.apple.com/#/additional-support

If a thief has managed to remove the Find My setting on the device then they likely also have access to a lot of your account information already.

Find the serial number or IMEI on your iPhone, iPad, or iPod touch - Apple Support

Browse it for section on what to do if you don't have your device.