Linux:

 

Makes zero sense 4G has to be off! If no 4G in that location or no 4G roaming the handset would just attach to 3G!

Edit: VoLTE should not need to be turned off as well

They sound like a pack of roaming clowns and I would not be dealing with them!

 

Yeah turned both 4G and VoLTE back on  - its working fine attached itself to Vodafone NZ using the following 

Please go to Mobile Data -> SIM -> SIM Applications.
You will see the following menu:

• Country
• Mode
• ICCID

select *Mode >
set it to *Manual >
set *IMSI 23 from the list.