Most 365 mail admin work doesn't end up touching the routing stuff, domains, or DNS records too often, so I'm by no means an expert. Last year I got rid of the last on-prem exchange servers in our environment. Here are my thoughts anyway, for what its worth.

At my workplace, domain as internal relay was used as part of our hybrid exchange setup, where we still had an on-prem exchange server largely for recipient management (for stuff connected to AD objects and thus mastered on-prem instead of in the cloud) and for a mail relay for internal recipients so that automated emails coming from legacy systems bypassed all filtering. I'm not familiar with other use cases.

Stuff that may not apply (minimize the lift)

I would approach this by using it as an opportunity to raze those hundreds of redirects. Surely the recieving systems have other ways to categorize incoming email than destination address. Stuff like system to system you could probably add shit in the body text and change the filters on the recieving end. So each external system would only have one destination address. That's ideal world though and probably touches a lot of shit outside your control.

Second thing is that I would look into setting the destination email addresses directly in the sending system. It takes management out of your hands, but why does any of this need to hit your infra in the first place? Again, that's ideal world and also probably touches shit you don't control.

Point is, I'd look to minimize how many of these things you actually have to deal with, because they'll just keep being a problem and a pain in the ass to manage forever otherwise. That's the real underlying problem, if you can do anything about it.

Stuff that more directly lines up with your ask:

If you can script routing rules you can probably figure out scripting the creation of contact objects in 365, and export of them to csv for verification.

PowerShell is going to be your friend with Exchange Online/365, and most things Microsoft. Exchange Online has a dedicated module (think library if you're used to terminology for other languages).

You can make a csv with the internal email address, external destination address, internal contact name, display name, and whether or not it's hidden from the address book (do end users need to send to it?). I'd reccomend using some clear prefix in the internal name to keep them obvious compared to any other contacts not related to this fuckery.

You could use full mailboxes and forwarding rules on each one but that increases complexity significantly.

In PowerShell, you'd connect to exchange, import the csv, then foreach over the csv contents throwing the values from it into New-MailContact.

If you want to be fancy you could wrap New-MailContact in a try/catch to spit failed ones out into an array and export that back to csv at the end for review.