Isso depende da implementação e da posição em que o seu ponteiro original (i.e. antes de chamar
realloc()) foi alocado.
Eu não vejo motivos para, numa implementação trivial (usando listas encadeadas de blocos livres e/ou ocupados), uma chamada a
realloc() encolhendo uma região de memória provoque movimentação de conteúdo. Em outra palavras, eu ACHO que o código
char *old_p, *new_p;
old_p=malloc(50000);
new_p=realloc(old_p, 1000);
printf("%s\n", new_p==old_p? "igual": "diferente");
poderia sempre imprimir texto "igual" na tal implementação trivial.
Se isso for verdade e o seu ponteiro original tiver sido alocado no final da memória, quando ele for encolhido a memória liberada será devolvida ao final da lista de blocos livres, e poderá até ser devolvida ao SO.
No entanto, se você já tiver recebido o bloco original numa região que não o final da memória do programa, ou se tiver alocado outros ponteiros entre a chamada a
malloc() e a a realloc[/i]() que tenham ficado numa região de memória após o final do bloco da primeira alocação, você pode, sim, ficar com um buraco. Tal buraco pode vir a ser ocupado por outras coisas no futuro, desde que elas sejam menores do que o tamanho do buraco.
Se você sempre começar com a alocação de blocos grandes que depois podem encolher, fazendo isso várias vezes seguidas ao longo do programa, pode ser que, dependendo da implementação, fique com muitos buracos grandes, efetivamente limitando a quantidade de alocações que você pode vir a fazer ao longo da vida do programa.
Dê uma olhada em
http://en.wikipedia.org/wiki/C_dynamic_memory_allocation, particularmente na seção "Implementation".
Considere a possibilidade -- se for viável, claro -- de alterar o algoritmo para começar com pouca memória e crescer somente quando for necessário, e aos poucos. Pode não eliminar a fragmentação, mas possivelmente vai deixar buracos menores.
