Maybe I am just being stupid, but the following occurred to me:
Most modern cell phones and smartphones - at least all the ones I have had in my hands in the last several years - have a slot for a memory card as well as for the SIM card. They will work just fine without it but it does give you a much greater memory capacity. At least many of them - for instance my present Samsung Galaxy S5 - give you the option of storing your contact list (and perhaps other kinds of data, I haven't fully explored this yet) in the phone memory, on the memory card, or both. If you store the data on the memory card only, at least you have the possibility of physically removing the data from the phone if and when you desire, and without impairing the function of the phone.
You can also (at least on the S5, but I suppose on all other comparable smartphones) shift data back and forth between phone memory and card memory, and you could theoretically even keep two entirely separate lists of contacts, one in the phone memory and one on the card, and switch back and forth between them as needed.
In the case of a lost or stolen phone I don't suppose this would make a difference, but having purchased my new smartphone "straight up" (paid in full - I hate owing money on anything, never bought even a car on installments) I am rather careful about keeping control of it. I never cease to marvel at the expensive smartphones people keep loose in their so easily pickable back pockets! - never mind the risk of sitting on the damn thing <G>. First thing I did after receiving my new smartphone was to buy a really strong case/holster for it (there are several, I chose an Otterbox Defender). It remains clipped to my belt, under my jacket. Of course someone could pull the phone out of the holster, but probably not without my noticing it <G>.