Apple Mail Address already in Use

Unfortunately I registered the wrong E-Mail Adress on the wrong Phone in the Apple iCloud Dashboard. I have of course deleted the Mail Address but as son as I want to register the same Email Address on the right phone it still says. Address is already in use.
How can I reactivate the Email?