This support question covers my issue exactly. http://www.gravityhelp.com/forums/topic/fails-to-add-user-to-list-have-to-recreate-mapping-after-list-updates - see the last entry.
I have spoken with MailChimp and they say that if you use their hosted forms then (unconfirmed) subscribers can resubmit their details as many times as they want and still receive opt-in emails. Apparently though if they do this through Gravity Form MailChimp Add-on form then they don't receive the "new" opt in email, as they are stuck in "unconfirmed" limbo - the last post in the above link lays it out perfectly.
Is there a way to resolve this? I don't want to have to have to replace my all Gravity forms with the hosted Mailchimp ones because it's time consuming and I've paid for Gravity Forms to work!
Any help would be appreciated.