La cuestión también es: el programa es para tu cuartel o espera que pueda ser consultado desde fuera? Usar una base de datos requiere el uso de un gestor de base de datos. Me imagino que usaréis Windows, por lo que no tendrás que preocuparte del acceso/uso desde otros SO.
No te recomiendo usar Access porque cuando empiece a crecer el fichero serán problemas. Algunas opciones ya te las ha comentado Guitarrista. Tendrás que elegir entre las opciones gratuitas o las de licencia. De igual forma, en el caso de consultas, ¿es que cualquier equipo de la oficina que quiera hacer consultas va a requerir que se instale el programa cliente de manejo de base de datos para poder acceder a la BD (que se encontrará en un servidor)? ¿O vas a desarrollar un programa cliente? Recuerda que también puedes hacerlo via web (tiene más trabajo pero evita muchas restricciones para el cliente y que tenga que instalar un programa): montar un Apache (no uses el Internet Information Server, IIS) con MySQL y realizar una interfaz en PHP, ASP.NET o JSP.
Existen
paquetes que incluyen ya eso. Que es instalar y listo, como es el caso de Xampp (el cual uso).
Y otra cuestión más importante, ¿tendrá que intercambiar datos con otras base de datos? Si ese fuera el caso averígualo para que tú no uses un motor de base de datos que no se muy compatible con el que tenga que intercambiar información (porque tendrás que crear un módulo "puente", que permita la comunicación y la conversión necesaria de datos). Así como configurar SSL para conexiones seguras. Pero repito que la mayoría de todo este royo es por si el programa permitiera ser consultado desde fuera (cuando digo desde fuera no me refiero desde tu casa, sino de la red vuestra privada si es que teneis alguna).
Saludos