I'll attempt to answer your questions as best as I can. I have significant experience with market research.
"How many questions are appropriate to put on a questionnaire? Let's say that we have ~8-10 questions. We don't want companies or more specifically the individuals at each company feeling like we are taking up too much of their time."
You are asking about the cross-section between number of questions and time consumption. Often, the issue is not the number of questions but rather the clarity of the questions. If each question is succinct and worded AND organized in a way that is sensible, the questionnaire may actually be completed in a very short amount of time.
A suggestion I would make is that you construct a questionnaire with all the questions you have and give it to someone who is not involved with your startup or has a limited awareness of the hypothesis. This can help you understand the MAXIMUM amount of time it takes (from the eyes of someone with no/limited background of your idea). Not only will this show you questions that were not worded well/clearly but you can now start "trimming" the questions. This is a rinse and repeat exercise.
If your questionnaire contains a lot of open-ended questions another way to go about this is to interview 1-2 people who are your customers (may have to pull relationship strings with this idea). For the open-ended questions you have in your questionnaire, ask the 1-2 customers to list all possible outcomes. By brainstorming with 1-2 customers you can identify a majority of these outcomes. Then you can make those multiple choice or check boxes minimizing time to completion. But just remember to give your respondents the option to select 'Other' and specify what they are referring to. If you do this, you can still include the text box for them to further explain if they so desire. The con for this particular strategy is that by providing a multiple choice/check boxes type of question, you are leaving the open-ended answer part of the question at the respondent's discretion. This will result in significantly fewer open-ended responses.
"Would it be beneficial to ask a smaller random subset of the total questions to each company? My thoughts being that there may be certain questions that some companies don't want to answer, and by having less questions it will be more quick and painless to answer. As the data set increases, it would still paint an accurate overall picture."
Your idea may work if your intention is not to see the "thought process" but rather just a general idea/cumulative opinion for each question. However, I would advise against this. You lose the integrity of the data by having disparate opinions for each question that cannot be further elucidated with follow-up questions. If you are unsure about companies answering specific questions leave them optional (obviously encouraging them to fill out all of the questions).
If you want any more advice, feel free to email me at lizhou.chang [at] gmail [dot] com.