I've just purchased Pokémon HeartGold for the Nintendo DS Lite and I was wondering if I could pair any Pokéwalker with my copy or would I need the Pokéwalker that was paired with the copy when new?
According to my research you can connect any Pokewalker to any copy of HeatGold or SoulSilver (HG/SS), assuming it is clean and not currently synced to a different save file of HG/SS.
If you do not have a clean Pokewalker (one that is not currently tied to another copy of HG/SS), you can reset it without the original save file on your copy of the game.
Go to the Pokewalker Connection Screen and hold [Down + X + L]. After that, you can connect the Pokewalker to the game to wipe the Pokewalker clean.
Note: it appears that 3DS devices and beyond have a hard time connecting to Pokewalkers. You will likely need to do this on a DS or DS Lite device.
Another note: I did not test this myself, I just did research.