Hey, I dream of a service like this and want you to succeed! But:
> Technically the IMEI isn't required for the network to function.
This is not correct.
Every carrier's SIM card firmware collects and reports the IMEI and modem manufacturer and firmware revision after AKA but before allowing any meaningful use of their network. There's nothing sinister about this; they have to do it in order to be aware of malfunctioning chipsets that crap all over their valuable spectrum. They most definitely do this on the first attach for a new IMSI, so they can block known-badly-behaving modems and update their IMSI<->IMEI mapping table. Verizon outright blocks the Quectel EC25 in many areas.
The only practical difference with IMEIs is that they are never sent in the clear. IMSIs are sent in the clear on the first network attach, which is the loophole that stingrays exploit. But most of your potential customers are more worried about carrier tracking than stingrays.
Have you found any carrier that will let you use random IMEIs, taking a different one each day like the IMSI? I haven't. Quectel hardware and a few Sierra devices will let you change the IMEI, so you can do the experiment. Osmocom has tools for sniffing the transactions between the SIM card and the baseband, although with an eSIM that may require some tricky desoldering work. Maybe you can solder an eSIM chip to a SIMcard-shaped PCB.