I'm a member on a fairly new, highly technical team in a software company that has ~3000 employees. Our mandate is to go across the company to research performance problems (hardware/software/process) and make recommendations.

Because of this, we're reaching out to a lot of teams who have never spoken to us before, and I'm having a hard time getting people to understand that we're serious and are thoughtfully approaching these problems. Just about every time I make a recommendation, I am asked "Are you sure?", and each time after I spend some additional time explaining why I'm sure, the information is accepted and the recommendations are put in place.

My question is: How can I establish credibility not only for myself but also for my team - who does not have recognition? Should it be a top-down approach, where we speak to managers and get them on-board and let them educate their team about who we are and what we're doing or do I pursue a more grassroots approach and try to approach people unofficially to chat about the subjects so that they can understand where we're coming from?