I came across this today and was able to solve it thanks to @Amaty's comment.
Here are some more details:
The core module Mage_SalesRule registers a global observer to run after each sales order is placed.
This observer increments the times_used counter on coupon codes, this is used for enforcing limits.
The code to increment times_used is inside the following if statement:
if ($order->getDiscountAmount() != 0) {
// snip
}
This means that if the order discount_amount is 0 no processing happens.
Source: https://github.com/OpenMage/magento-mirror/blob/magento-1.9/app/code/core/Mage/SalesRule/Model/Observer.php#L72-L133
Free Shipping coupons
Typically a Sales Rule set up to allow free shipping with no other discount will be set up as below:

One or many coupons are then created, a typical use case is multiple coupons valid for a single use per coupon.
Because of the logic around incrementing times_used when these coupons are used, if no other discounts apply, then the coupon will not be marked as used.
The Coupon Codes will however provide the correct "Free Shipping discount" and continue to work for later transactions. This means the merchant is discounting more than they intended with the free shipping coupon.
A Fix
I elected not to overwrite the existing core module's observer but rather create a new global observer of my own and use identical logic except for the following:
if ($order->getDiscountAmount() == 0) {
// snip
}
This means the core observer will run and process all coupon_codes for orders with a DiscountAmount. The observer that I've put together will run for all others - this is so I can leave core untouched without double counting coupon usage.
I have published this as a module here: https://github.com/etailer/Etailer_CouponUsed/
I also wrote a Magento shell script that iterates through all orders with no discount_amount and a coupon_code present. It then increments their times_used. This is optional but I found it very useful to quickly void all the used coupons. It can also be extracted and used standalone if you've fixed the core issue some other way.