Testing and validating startup ideas

In the article "How I Quickly Test and Validate Startup Ideas", David Berube explains how he used Google Keywords and Microsoft adCenter to gauge interest in potential startup ideas. While initially found this idea intriguing, I now question its  effectiveness. 

Last semester in A Service Design workshop with April Stare, my team and I developed a service which I believe solves and important problem, and has the potential to be a viable business. We used David's technique with poor results. In his view, we should have scrapped the idea. I believe the problem wasn't with the idea, but with either the method, or our use of it.

Our service connects research scientists who need access to specialized instruments with laboratories who have them. The acquisition process for these items involves at least 3 stakeholders and can take up to year to complete. It was difficult to figure out what keywords people would use to find our service. We ended up targeting words like lab sharing, lab equipment rental, as well as 10 top machines universities purchase in the top 3 scientific research hubs in the US. The results were awful. Out of 200 placements, only 1 person clicked. If we had phrased it differently would we have gotten better results?

How do you use search to validate an idea for a new type of service and involves multiple decision-makers?