Basicamente, você precisa de um banco de dados. Excel pode fazer o trabalho por um tempo, mas vai ficar confuso e muito grande em muito pouco tempo. Eu recomendaria usar um banco de dados. Você poderia começar com algo como o Access (que permitirá que você crie formulários) ou o MySQL, se você quiser um banco de dados livre, mas eu não sei o que você pode obter para criar formulários para o MySQL. O SQL Server seria a minha escolha, e há uma versão Express gratuita para até cinco usuários e um tamanho razoável de dados, com uma atualização perfeita para o SQL Server completo, caso você precise dela.
Em seguida, a outra opção é claro para entrar on-line com algo como o Google docs.
Existem tantas opções que acho que você pode obter respostas melhores se puder especificar quais entradas, com que frequência, quantos PCs estão envolvidos, se estão todos em um único local geográfico, quantos tipos de pesquisa estão lá e se eles querem outros relatórios do sistema, como encontrar todas as partes de um determinado provedor ou de um lote especificado.