Хранит ли сотовый оператор у себя информацию обо всех IMEI телефонов, в которые вставлялась сим карта?

Да.
Какая симкарта, какой IMEI , в какое время и на какой станции зарегистрировался, когда и с кем связывался, что и кому отправлял, плюс еще некоторая техническая информация позволяющая определить местоположение телефона в это время.