This error means the email address was removed or unsubscribed from Mailchimp at a certain point in time.
Mailchimp does not allow emails to re-subscribe over the API once they have been deleted or unsubscribed.
It is possible to manually add the contact in Mailchimp again. Once this has been done, it will be kept in sync, just like your other contacts.