There seems to be a disconnect between what Thor tells Banner (he's been on Sakaar for two years, since the events of Age of Ultron) and what probably happened. We see that time moves faster on Sakaar than Earth or Asgard. This is first shown when Loki and Thor fall out of the Rainbow Bridge within seconds of each other, but Loki has been on Sakaar weeks before Thor arrives. Even the Grandmaster admits that time is different on Sakaar.
It seems likely to me that Hulk had actually been on Sakaar for decades, maybe even centuries. How long was Hulk on Sakaar before Thor arrived?