Brett,
Having just re-insulated my icebox for the exact reasons you note (soggy insulation resulting in high duty compressor cycling and condensation on the outside walls) I can attest the job is indeed 'quite a project'. Not really that hard, just somewhat time-consuming, disruptive and messy.
If your insulation is original then after 35 years or so more than likely it is completely shot. In my case it looked to be simple 'expando-foam in a can', sprayed onto the icebox. Once I removed the icebox it literally fell off in soggy, wet chunks.
I knew re-insulating the icebox properly would be a big job. Trying to avoid the disruption I examined many, many different alternatives including 'by-passing' the whole thing and installing a 12/110v Engel drop in. Not a viable solution for me because while nice, the Engel is either a refrigerator or freezer, not both.
After literally years of contemplation and talking to refrigeration experts I never could come up with a easy solution. Finally accepting there were no shortcuts I just finally bit the bullet, ripped it all out and started from scratch. Once the icebox tub was out I was able to re-gelcoat the tub inside & out, fabricated forms around it and poured 2 part closed cell foam to form a solid structure around the icebox tub.
In the end it was totally worth it. I now have ice cold drinks and the compressor runs about 25% of the time saving me tons of battery life.