We were in the same boat back in the mid 90's and are starting to be in it again in a new sector.
In the market we were selling our software in, it was always difficult for us to find hard numbers on how many end users our competitors had. I hate to say it, but for us we would normally dig one company at a time.
Normally we would look for news a competitor would be putting out. Sometimes we would have an extra person with us at trade shows and we would send them around to do recon for us (yes, I'm sure most companies do this). There was one time one of the industry rags that was prominent in our industry put out a study about what software packages people were planning on purchasing in our industry. That was good for us because we found out we were number three in an industry that had hundreds of software companies in that vertical market.
Personally one of the ways that I have found to glean some good information is to determine what technology your competitor is using to develop their software in. If you know that, sometimes you can go to that companies website and find whitepapers that will give you VERY detailed information about that company. In this instance, we knew the technology a particular company was using and found a technical blurb on that technology companies website about that company using their software to develop their solution. The flat out said in the article that this company had around 250 companies running their software.
I'm sure there are a lot of other tricks to the trade. Would love to hear how others have found out this information. I'm sure some just call their competitors acting like a possible lead and just ask outright how many companies use their software. I know I would. :)