Single versus multiple CPTs

Hi – I could really use some help. I plan to have a national directory with multiple categories and sub-categories. I set it up with 12 CPTs to help organize the search for the user. However, I see that if the user doesn’t know that they need to select a CPT before typing in their query, or if they select the wrong CPT, zero results will display. So, now I am considering going back to just one main umbrella CPT and having lots of categories and no sub-categories, just to ensure that my users will get search results every time.

So, instead of having:
Health (CPT)
– Acupuncturists (Health category)
– Massage (Health category)
Restaurants (CPT)
– Chinese (Restaurant category)
– Italian (Restaurant category)

Now I would have:
Businesses (CPT)
– Acupuncturists (Business category)
– Massage (Business category)
– Restaurants-Chinese (Business category)
– Restaurants-Italian (Business category)

Issues:
– I would love to have the multiple CPT organizing structure, but I don’t want to risk users not getting a search result, so I am in a quandary as to how to proceed.
– I wish that businesses could have two CPTs (eg “All Businesses” and their relevant category eg “Health) without having to enter the business twice. That way, users would be ensured of getting a search result regarding of their selecting the correct CPT before searching. Is there any way to do this with one business entry?

Question:
If I decide to go with just the one CPT (All Businesses) and many categories:
– What could be the issues down the road if I have many thousands of listings?
– Is it possible to use CSS to organize the Categories on the homepage into sections? E.g., all Home Service related categories under one subject heading and all Food related categories under another heading? So the page looks more organized than just one long list of alphabetized categories under the one CPT Businesses.

Do you have any recommendation for me on how to best set up my structure?

General question: How many business listings can GeoDirectory effectively work with? I am hoping to have tens of thousands. Will GD work well with that many listings?

Thank you very much! I eagerly await your reply…