Ops! Le mie scuse... quando ti ho scritto quel pezzetto di codice (che del resto, come ti ho detto, non era nemmeno completo) ero molto di fretta e non ci ho ragionato su molto...

Sono andato a riprendere la mia implementazione dell'algoritmo ricorsivo nella lista. Come ti dicevo, con la versione ricorsiva non esistono casi distinti: che sia in testa, in mezzo, o in fondo alla lista non fa alcuna differenza. Funziona anche se viene chiamato direttamente su NULL.

[L'ultimo parametro è una funzione di comparazione, ho implementato una lista di void* così che possa essere usata per qualsiasi tipo di valore e questo richiede una funzione per fare i confronti]

codice:
Node* list_remove(Node* currP, void* value, int (*cmp)(void*, void*))
{
    // Fine della lista
    if (currP == NULL)
        return NULL;

    //Nodo trovato
    if (cmp(currP->data, value) == 0)
    {
        Node* nextP;
        nextP = list_remove(currP->next, value, cmp);
        free(currP);

        return nextP;
    }
    else
    {
        //Controlla il resto della lista
        currP->next = list_remove(currP->next, value, cmp);
        return currP;
    }
}
P.S: dimenticavo: inoltre questa elimina anche eventuali doppioni.