At least in LTE, the IMEI isn't a necessary part of connection setup. The network identifies the user seeking to connect by a temporary identifier if one of those is allocated or by the IMSI if that's all the user has. After the network and user pass a mutual authentication procedure, the core network may optionally ask for IMEI.

The identifiers actually used over the air are the IMSI (normally written once at the SIM factory and never changed, used as a fallback if no other identity is available), the TMSI (assigned by the core network when the user attaches, can be reassigned at every attach, service request (return from idle to active state), or mobility event that the core knows about), and RNTI (assigned by each cell, changes at each handover, used to address each downlink transmission to the mobile and I think included in the CRC in each uplink transmission from the mobile).

If you just receive a random transmission off the air, you can get the RNTI; if you receive an initial signaling message to the core network you'll get the current TMSI if assigned; you'll see the IMSI only in case of a new SIM or a SIM where the core network has forgotten who it assigned that TMSI to.

There are also some temporary identifiers between the cell and the core network allocated when the cell starts talking to a mobile and released when the mobile goes idle, but these never reach the mobile.

The core knows the IMSI and optionally IMEI of everyone connected. In normal operation, each cell only knows some temporary identifiers (it has the opportunity to record IMSI if the mobile sends it, but the mobile doesn't normally do that).

All the details are available from 3gpp.org, and I can be more specific about which section of which doc if anyone actually cares.