I was contemplating filing a FOIA request with a NJ state agency but do not know if they keep the state based companies in one searchable database? If they do not have this information what other sources can I use to obtain this data?
Perhaps not all, but a great amount.
Orbis is probably one of your best shots. They contain listed and private companies that you can filter by address. However, access is not free. One way to access would be to go through a university proxy.