I just talked to the business licencing office of my city and they would give me the previous 200 names for $20 but only if I specified a category (eg. contractors).

The names are cheap but there are lots of categories and just getting the new companies would requires that I buy the list of many categories.

These lists are then effectively out of reach of the average person and you are better off purchasing from these mailing list companies who buy them and resell.

I don't know if this is the same situation with other city departments though so you should check.