The barrel may very well still be serviceable after 20,000 rounds. A lot is going to depend upon how much abuse it saw. (i.e. are you regularly dumping 100rd belts, letting it cool between belts by swapping it out, firing in small bursts, etc.) A set of headspace gauges will quickly help you determine if the barrel is still in spec headspace wise.
However, you are going to get some throat erosion every time you pull the trigger. A barrel with 20K down the tube is going to have more throat erosion than a new in bag barrel. This may still be fine if you are using new brass case ammo, but take a barrel with 20K worth of throat erosion and brass that has been through a machinegun 2 or 3 times and you have the recipe for head case separation you are seeing.
Reloading can save you time/money but when you are talking about US Ord M60 parts cost it doesn't take many wrecked or damaged parts to quickly start negating the reloading savings. (not to mention the headache of a jammed up gun)
Guns like M16s where a whole new upper is less than $500, a barrel is sub $200, and anybody with two opposable thumbs can fix it in the field/range by dropping a new upper onto the gun the economics may make more sense to run reloads/steel case/ or surplus.
I would be surprised if the brass couldn't be removed from the barrel. It may just require sending it out to somebody who has the knowledge and tools to get it out without damaging the chamber or stellite throat insert.