I you haven’t already done so, I suggest contacting the New York Public Library. It’s possible the staff might point you in the right direction for archived business addresses.

They can likely tell you if it’s available in computer form or if a tedious manual search is required. You might find things more efficiently with their help rather than doing it strictly on your own.