In tutte le pagine è presente session_start()
le cose strane sono due:
1- sul vecchio hosting funzionava tutto bene
2- il problema non è sistematico, a volte la sessione rimane, altre volte scompare.

Potrebbe essere la RAM insufficiente ?