Comment 10 for bug 1014769

from network/manager.py:

@wrap_check_policy
    def deallocate_for_instance(self, context, **kwargs):
        """Handles deallocating floating IP resources for an instance.

        calls super class deallocate_for_instance() as well.

        rpc.called by network_api
        """
        instance_id = kwargs.get('instance_id')

        # NOTE(francois.charlier): in some cases the instance might be
        # deleted before the IPs are released, so we need to get deleted
        # instances too
        read_deleted_context = context.elevated(read_deleted='yes')
        LOG.debug(_("floating IP deallocation for instance |%s|"), instance_id,
                                                  context=read_deleted_context)

        try:
            fixed_ips = self.db.fixed_ip_get_by_instance(read_deleted_context,
                                                         instance_id)
        except exception.FixedIpNotFoundForInstance:
            fixed_ips = []
        # add to kwargs so we can pass to super to save a db lookup there
        kwargs['fixed_ips'] = fixed_ips
        for fixed_ip in fixed_ips:
            fixed_id = fixed_ip['id']
            floating_ips = self.db.floating_ip_get_by_fixed_ip_id(context,
                                                                  fixed_id)
            # disassociate floating ips related to fixed_ip
            for floating_ip in floating_ips:
                address = floating_ip['address']
                self.disassociate_floating_ip(read_deleted_context, address,
                                              affect_auto_assigned=True)
                # deallocate if auto_assigned
                if floating_ip['auto_assigned']:
                    self.deallocate_floating_ip(read_deleted_context, address,
                                                affect_auto_assigned=True)

This looks like it is trying to do the right thing, perhaps something is broken in db/sqlalchemy/api.py? I've written some quick and dirty unit tests that should massage this behavior out, but I can't get it to happen in unit tests. I seem to only see it on a live system