I'm really surprised nobody has mentioned a biodiesel blend as a solution.. It has high lubricity and raises cetane, and has some aromatics that may help maintain seal swell inside the pump.. it's about the cheapest solution you can find per gallon..
I'm suprised no one mentioned biodiesel either! Europeans have already pulled the sulphur from diesel, and now the require the addition of a small percentage of biodiesel. As little as 5% (B5) will provide the librucity that the sulphur fuels had.
Of course, not everyone here has biodiesel available in their area. And for you folks living in cold climates it can be hard to keep biodiesel from freezing solid. When mixed in a small amount it won't freeze as it mixes completely with petro-diesel.