Are they looking for the previous residents of your house, or just for the people who had your phone number before?
We had people looking for someone who used to have our phone number. This wasn’t so strange. We just explained that we didn’t know this person, and, no, the address they had for him was not our address. However, one evening, some people actually came to our house looking for this guy! Kind of unsettling, but easily handled. They must have looked in a reverse telephone directory and found our address when they looked up that phone number.
I wouldn’t worry too much. They’ll eventually figure out that the guy’s not there anymore and stop bothering you, especially if it’s the bill-collector type people like the ones who were calling us.
Not only are there internet reverse telephone directories, but there are also dead-tree versions. (At least, there were when I was in high school, which is before the internet really took off.) Larger public libraries often have them. I remember looking at one geared towards businesses–it had affluency ratings for different neighborhoods.