This is a bug in the deallocation order of the elastic IP address and
was introduced when CloudFormation went from single to parallel
AWS are aware of it, and hopefully they can get it on the roadmap to get
it fixed soon. In the meantime, the somewhat unacceptable workaround is to
run the remove-cfn stack again.
(We actually have a helper which runs the remove, and keeps calling
delete until it's finally decided to be deleted)