Then the object of my sympathy replies, "Oh, it's not your fault."
Of course it's not, you pitiable dolt.
This irritates me to no end, because it turns me from generous giver to guarded defender. Sorry has several shades, but most people can recognize "sorry I'm responsible" from "sorry for your misfortune" based on context.
For those that can't, I recommend the "sorry-prime" terminology. Sorry-prime (also written as sorry') is the derivative of sorry feeling; the slope of the emotion, if you will. It's not regret for your role in your friend's suffering, it's just general regret. Sympathy.
This can work with other emotions, too. Angry-prime, envy-prime... if you can feel it, you can probably feel the derivative. The only exception may be jealousy-prime.
Try it, because this is the kind of thing that needs to catch on in order to work. At least think of it this way: the next time you say you're sorry-prime, the object of your sympathy may still not know what you mean, but he probably won't correct you, either.