I also quite often have problems with an unknown IMEI when using MyPhoneExplorer (I guess that you are talking about the same program!?) and also when using Navigon, which also reads out the IMEI.
Just some days ago I found out that you don't need a full reboot, but that also a so called "Hot boot" is sufficient, which just needs a few seconds to complete. For this I'm using an app called "Rebooter (fast reboot)", but there are also other apps, just search in the Play Store.
@Quarx and
@Blechd0se: As far as I remember, the bug with the sometimes missing IMEI is there since CM10 or at least since the first custom kernels. I would be grateful if you could have a look into this issue!