Comment 7 for bug 1014769

This is odd, as there is specific code to remove the tenant from the floating ip if auto_assign is set in nova/network/manager.py:

 375 # deallocate if auto_assigned
 376 if floating_ip['auto_assigned']:
 377 self.deallocate_floating_ip(read_deleted_context, address,
 378 affect_auto_assigned=True)

cany you check if auto_assigned is set to true in the database?