MailChimp: Any unsubscribed e-mail address cannot resubscribe

In our MailChimp account (Account > Extras > API Keys) we’ve created and activated an API key.
We entered this key in “Enfold > Newsletter”, checked for the key and got a working connection.
We see all the lists which exist on MailChimp, including the list fields, number of subscribers and so on.

The integration of the MC-widget itself works smoothly as well. When you enter an e-mail address on the website, you get the DOI-e-mail and after confirming this, your e-mail becomes a part of the subscription list.

There is a huge BUT: once you unsubscribe from the newsletter, you cannot subscribe ever again with the same e-mail address.

We even fully deleted contacts in the MailChimp account (by choosing “Actions > Delete” and then choosing “Delete and Remove” or “Delete and Archive” and confirming this with “DELETE”). Does not solve the problem as well.

When I try to manually re-add an address in MailChimp itsself, I get:
“This contact was previously removed from this list. To rejoin, they’ll need to sign up using a MailChimp form.”

But then again, when I try to do this in the widget on the website, I get:
“We are very sorry but something went wrong. Please try again later.”

—

We also checked https://mailchimp.com/help/delete-contacts/ before which was recommended in this thread https://kriesi.at/support/topic/mailchimp-unsubscribed-emails-unable-to-resubscribe/ which seems to describe the same issue.