I think Scott Hall is underrated as a wrestler because people focus on his issues. That being said, his issues stopped him being trusted with a world championship. Razor Ramon was great, and nWo Hall better, but he squandered his chance to be the main man.
Unlike Koloff, who beat Sammartino to end his reign. The gravitas of that cannot be underestimated. Koloff would beat Hall, outmuscling him and making up for their height differential.
Hall was a big success at a midcard level, but so was Koloff in the NWA, and he was in the main event a lot more often than Hall ever was. Koloff wins a tough encounter with the bear hug.