I seem to recall Hiking Boots being banned in the rules at one point, but they aren't anymore. So were they banned at one point or is my memory wrong?

Hi! Yes, the Hiking Boots were banned up until 2018, so every run before then would not be using them.

Thank you. What was the reason for why they were banned and then unbanned?

They were banned because it required pre-run preparations, which was to walk for 10,000 steps before the run (or set the 3DS time to a date where you did 10,000 steps but it still required you to do 10,000 steps), and according to Fretzi it was to make it so new runners weren't required to shake their 3DS or walk just for a run.

They were unbanned after a poll was created in 2018 to see if people want to see it unbanned (with basically everyone voting yes, but that data is gone), so it was unbanned. The Hiking Boots ban was a pretty early decision that stuck around for a few years, ultimately, which people after a while disagreed on.