You are right, IMEI is not sent in LU request messages, so no way to see the IMEI in the traces.
What you can do to check:
1. go to Astellia AA
2. open the latest AA base (real time analysis)
3. take distribution of IMSI doing the most failed LU – cause (Rej)IUH
4. Reactivate 5 of those IMSI with test numbers and call them immediately to know which phone they are using
5. Get the same phone to test yourself the scenario.