David,
Your last comment applies for cleaning up indexes as well ? We performed a simple test in our production database to understand behaviour and we got a result that surprised us based on your last comment.
We basically started a VACUUM on a given table, waited for one index to process (captured cleaned rows count) and cancel the VACUUM. When we run another VACUUM on the same table the dead rows removed from the first index was a number slightly higher than the value logged on the first VACUUM. This behaviour made us feel that the work done to clean dead tuples on the first index was performed again.
Thanks!