La forma mas sencilla de realizar la operación es utilizando al contador como bandera de estado, de esta forma:

for (i = 0; i < m; i++)
   if (strcmp(nom, P[i].Nombre) == 0)
      break;
if (i != m)
   printf("%s esta en la base de datos\n", nom);
else
   printf("%s no esta en la base de datos\n", nom);

----

En cuanto al prototipo de las funciones: se recomienda por "buenos modales" y en ciertos casos es obligatorio (por ejemplo con funciones variadicas).

Cuando no se tiene acceso al prototipo de una función se infiere este en base a la primera llamada asumiendo:

1) La función retorna un valor de tipo "signed int".
2) El numero y tipo de argumentos esta dado exactamente en la llamada.

En el caso de DickGumshoe la única llamada a "strcmp" es:
Y como esta coincide con su prototipo no hay problema.

Pero si se tratara de una función que retorna algún otro tipo de valor (por ejemplo un "double") o una de las funciones printf/scanf/etc si seria un error.

Un saludo