Forcing unique account emails after years of not

After eons of building on top of legacy systems, my company backed itself into the proverbial corner.

We are in the unique position where multiple user accounts can share one email. This is fine, for sign-in purposes because they have multiple ways (read: username/unique id/etc) of signing onto their account. This has worked up until now. We would like to allow people to sign in with their emails as well, but this would require the email to be unique.

The unfortunate scenario is that the best solution/workflow is to ask the user to choose a new unique email to be used for logging in. Which kind of feels like saying "We can't let you use your original email, you'll have to choose a new one, but the duplicate account will be able to use it because as soon as you change your email, then it's technically unique." This, to me, doesn't seem particularly fair, or indicative of good UX.

So the natural thought process is then to make a first come, first serve system, where the first person can lay claim to the email, and the duplicate account will have to choose a new one. The unfortunate scenario here is that we send billing information to these emails, and we can't have an account be email-less until they change it manually.

Does anyone have a better idea than the two listed above in regards to user experience?