It's generally safe to refreeze food that was never above 40 degrees. The rule of thumb about not refreezing things is largely due to changes in flavor and texture. With vegetables or meat, freezing, thawing, and freezing again can cause cell walls to degrade, redistribute fluids, etc. With a stock this is not a problem.
In general when you want to refreeze anything you should thaw it in your fridge rather than on a countertop or in open air. With a soup, assuming you thaw the stock below 40 degrees, then cook, then handle properly, you should have no problem doing this.
I make and freeze my own stocks all the time, then make soups from them and freeze leftovers. I've never noticed a quality issue in doing so.