Qué tal con indices?
Uno desde el principio hasta la mitad y el otro desde el final hasta la mitad. Si las letras en el índice son iguales mueves el índice, sino paras el bucle.
Compruebas si el índice ha llegado a la mitad, si es así es un palíndromo.

Hola,

Como dice MAFUS, con índices sería una buena solución, algo así como:

Siento str nuestra cadena...

int total = strlen(str)-3; // Si tenemos 4 letras, la última será la número 3
int i;
int ok = 1; // Son palíndromos hasta que se demuestre lo contrario
 
for (i=0; i<total; i++, total--)
{
  if (str[i] != str[total])
  {
    ok = 0;
    break;
  }
}
 
if (ok)
  printf ("Son palindromos\n");

No sé, algo así.

También puedes coger un algoritmo para darle la vuelta a la cadena, por ejemplo http://totaki.com/poesiabinaria/2009/05/volteando-cadenas/ y comparar las dos cadenas, con strcpy() si la cadena al revés es la misma que la cadena derecha, ya lo tienes.
El segundo método es más costoso, pero más general y más cómodo.