I have been in this near exact situation, except that for me it was someone using one of my legit email addresses that isn't (or wasn't) also an Apple ID. Appl

I have been in this near exact situation, except that for me it was someone using one of my legit email addresses that isn't (or wasn't) also an Apple ID. Apple Support was happy to shut down the account for me given that I didn't want access to it, but instead just wanted it disabled so that it couldn't be used. If you're trying to get access to the account Apple is going to be understandably resistant given that even if it was setup in error it may contain sensitive information sync'd from a device. You can request that they disable the account and make it so that the email address cannot be used to sign up again. Given that this was a random address you may need them make some kind of filter for your domain. Also, given that it sounds like you catch all email that goes to any address for your domain you've basically removed a way to know if addresses are in fact legit since they don't bounce email. That may be why your domain was used for this purpose in the first place.