I hate to disagree but I think something weird is going on here still:

This is not a case of used up certificates, for example for a new order I get two certificate entries:

certificate_id name value user_id order_id purchaser_id cert_code
9 Gift Certificate 2.00 7 NULL 3 9-M4BSjb9aRVus
8 Gift Certificate 2.00 7 NULL 3 8-oHQLE5nGTlmL

I think the issue may be that for different order states the order transitions through, you are generating multiple certificates in your order update case?

Also interesting condition I have seen with user emails. Sometimes the user email isnt sent until the order is in the completed state. But a user has be created (but never accessed) in Drupal. This leads to the wrong email being sent because a user does exist even though the user has never been notified or used the account.

Thoughts?

UPDATE:

I changed my local version to only issue new certificates on the payment received order update case and it is definitely much better behaved. I also added a check to see if the user account was ever accessed in determining which email type to issue.