I have had 5th gear issues for the last 60K on my truck (4 rebuilds + now a new trans), but I tow a rather heavy trailer (15.5K). My opinion currently is to purchase a "new" NV4500 from Midwest Transmission. He still had some left a few months ago. I have a new one in my truck and have towed over 3K miles with it so far. Seems to be working well, time will tell.
My 2nd ST rebuild 5th and 5th countergear looked exactly like yours, similar situation, was driving 60mph pulling a very slight slope and then KABOOM, no more 5th gear. The rebuild had 6K miles on it, less than 4K towing. I was running Amsoil GL4 at the time.
My next rebuild was Midwest trans, and the ST mainshaft was re-used. All gears were Cryo treated and it lasted for 25K miles (but about 4-5K miles towing again). Only broke 3 teeth off 5th, none on countershaft. 5th nut did not back off, but the 5th gear was worn severely (could rock it back and forth on mainshaft) and there was 0.015" space between nut and gear.
If you get a new trans, there isn't a core and you could have your old one rebuilt as a backup spare. That is what I have currently. The NV4500 isn't a reliable trans if you tow heavy, so a backup keeps the truck available with only a trans swap. I have gotten to the point I can swap mine in the garage in about 6 hrs.
The alternative is a G56 conversion - but the cost is $$$$$. It figured to just over $6K total cost, which is why I had to just get a new NV4500. I talked with several TDR members that have done it, and it would be worth the $$ if you can afford to put that much into your truck according to all of them I spoke with.
Jeff