I would link to a sitemap page from the home page.
On that site map page link to all fifty states.
Each of the states can have the zip codes as a link to a information page, with the professionals listed and link to each one.
Feed a high
PR link to the main site map page, and indexing will be a breeze.
Peace