SIM800L only working on EE (UK)

I have successfully used an ASDA mobile SIM card for my weather station project, but unfortunately ASDA mobile are now moving their network from EE to Vodafone and everything went downhill from here.

I got the replacement SIM card, and the SIM800L will no longer register on the network. The LED either flashes continuously or perhaps between 12 and 18 times, then after a short pause continues.

AT+CREG?
+CREG: 0,2
OK

AT+COPS returns a few networks including Vodafone.
I've then tried a O2 prepaid card, with same result. AT+CREG? indicates it is trying to register, but fails to register.

AT+COPS=?
+COPS: (1,"O2","O2 -UK","23410"),(3,"T-Mobile","TMO UK","2343

Both cards work fine in my phone.
I then tried my Virgin mobile SIM card (which uses the EE network), and the SIM800L registers in under 10 seconds successfully with the network.

I am not sure where I'm going wrong, or if some technical reason I don't begin understand, the SIM800L can now only connect to EE network in the UK.

I'm guessing that is because EE is the last remaining 2G network

Good thought. Having looked into this possibility, currently all networks in the UK (EE, Vodafone and O2) as well as their MVNOs still support 2G. A lot of technological solutions still seem to rely on GSM modems. Interesting reference here that mentions no definite time plan for 2G shutdown.
The SIM800L does show up all networks with AT+COPS=?
Actually, it finds a "T-Mobile" network, which I presume is EE and a relict from when T-Mobile was its own network before migrating to EE.