Risolto!

Lo script che terminava con il redirect, sebbene non contenesse codice HTML e quindi fosse un unico flusso di istruzioni PHP, aveva un tag di chiusura "?>" (seguito da un tag di riapertura ovviamente) a metà script.

Evidentemente per qualche ragione (versione PHP, settaggi) su questo server la chiusura del tag comportava la spedizione degli header, mentre sull'altro server no.

Adesso sembra funzionare tutto perfettamente in ogni caso, grazie dell'aiuto.

Se poi qualcuno riesce a spiegarmi meglio il perchè di tutto ciò... meglio ancora