As someone who literally just implemented Resque for our Heroku hosted app yesterday and is about to add billing to it I'd like to know a little more. What percentage of jobs end up getting killed? Are you flagging those jobs somehow so that you can rerun them and check if the 3rd party service already received them?
He explained this in the post a little bit, but when you deploy to Heroku, scale down dynes, etc., Resque workers will be killed, and if they're processing a job the job will be killed. He also mentioned that they use Resque Retry to retry the jobs that were killed. You just need to trap the signal and perform cleanup, which is typically something you should be doing.
Even if Heroku is working 100% normally and your code is working 100% normally, your jobs will get killed. The workers get SIGTERM'ed once per day minimum as dynos cycle. The more workers you have in flight on average, the more you will see this. The best thing to do is make your jobs retriable, meaning they are idempotent or otherwise can pick up where they left off. Then use resque-retry to have them automatically retry. That's what we've done, and now the only failed jobs we get are legit issues and not Heroku