If I have deleted an address, is it gone permanently?

Addresses are not actually deleted from the system, they are moved to the inactive list. Depending on whether you unsubscribed or trashed them, they will appear in that inactive list. If you want to permanently delete an email address, you must delete them again from the Inactive list.