Le domande sono:
1) il problema è proprio il SID? se sì come mai tutto il resto funziona? (condivisione cartelle, internet, ecc.)

Mediamente quando si reinstalla da 0 un server in special modo sbs si possono incorrere a questi problemi. Di solito si riesegue un join out e join in al dominio nuovamente, altrimenti potrebbe non prendere piu le policy. infatti se vai nella schermata computer di sbs, vedrai che ci sono ancora i computer ma se provi ad attivare un qualsiasi servizio potrebbe non funzionare.

2) se è il SID sarà probabilmente necessario eseguire l'esci/entra dominio su tutti i clients. Dato che sono oltre 30 mi chiedo se ci sia un metodo alternativo (ricordo vagamente un vecchio software NewSID...ma non credo esista più). Come si procede in questi casi?

A manina pc per pc.. oppure prova a fare una ricerca su internet che lo trovi sicuramente.