Io comunque farei così:
codice:
#include <stdio.h>

int aggiungi_stringa (FILE *f, char *str)
{
    int count;

    if (fseek (f, 0L, SEEK_SET) != 0)
        return 0;

    if (fscanf (f, "%d", &count) != 1)
        count = 0;

    if (fseek (f, 0L, SEEK_SET) != 0)
        return 0;

    fprintf (f, "%010d\n", ++count);

    if (fseek (f, 0L, SEEK_END) != 0)
        return 0;

    fprintf (f, "%s\n", str);

    return 1;
}


int main (void)
{
    FILE *f;

    /* Si assicura che il file esista! */
    if ((f = fopen ("prova.txt", "a")) != NULL)
        fclose (f);

    /* Aggiunge delle stringhe */
    if ((f = fopen ("prova.txt", "r+")) != NULL)
    {
        aggiungi_stringa (f, "ciao");
        aggiungi_stringa (f, "hello");
        aggiungi_stringa (f, "andbin");
        aggiungi_stringa (f, "test");

        fclose (f);
    }

    return 0;
}
Nota 1: non ho messo i controlli sui valori di ritorno delle aggiungi_stringa().
Nota 2: non ha la pretesa di essere perfetto! Si può sicuramente migliorare il test sulla fscanf e mettere il test sulle fprintf.