Machine stuck in 'pending' state cannot be terminated

Using juju-core 1.13.1-1~1628~raring1 against an OpenStack provider. Sometimes when provisioning many machines, some instances fail to get an IP. The result is an instance that is 'Active' in OpenStack's eyes, but still 'Pending' in Juju's. If I later attempt to destroy the service unit and terminate the machine, the unit is destroyed but the machine never terminates. Instead, I end up with something like:

environment: precise
machines:
  "0":
    agent-state: started
    agent-version: 1.13.1
    dns-name: 10.5.0.4
    instance-id: 982d3feb-fa72-4c26-911b-48023316d5d1
    series: precise
    hardware: arch=amd64 cpu-cores=1 mem=512M
  "9":
    agent-state: pending
    dns-name: 10.5.0.14
    instance-id: c97fd63a-fb33-4071-bcf6-4d001cc21013
    life: dying
    series: precise
    hardware: arch=amd64 cpu-cores=1 mem=2048M

Attempting to re-terminate the machine does not help. If I terminate the instance manually via nova, the machine stays in the environment as pending.

FWIW, I am using juju-deployer (+ python-jujuclient) to reset the enviornment.

Attached is machine-0.log.