Basta che riflashi il tuo attuale firmware con Odin.
Se è il caso potresti anche valutare il deep clean 1 o 2 a secondo del risultato che vuoi ottenere le guide sono nella sezione modding.
Prima di queste operazioni e quindi prima di togliere il root vedi se recuperi il thread sul forum XDA per il recupero IMEI e cartella EFS, magari per qualche operazione è necessario il root.
In ogni caso anche se l'operatore ha detto che non risulta il blocco IMEI non è detto che abbia detto la verità, a volte sono talmente svogliati che rispondono tanto per rispondere, come dimostrano i thread che ho linkato.