I was reading that the reason that why even legit AT&T SIM cards (the ones that came pre-installed) could not be used to activate a previously unlocked iPhone could maybe be because the IMEI number had been modified by the unlocking software. This could possibly have resulted in some kind of mismatch between the phone and it's original SIM.
I don't know for certain whether this is the case, but while we all know unlocking itself isn't illegal, I'm sure I heard a while back that modifying IMEI numbers is.
The unlocks aren't modifying the IMEI. What's happening is that some of the unlocks (iUnlock/AnySim) rewrite a section of the firmware code that is used to validate what a phone's IMEI is. When their unlock patches are applied, this modification has no effect and the correct IMEI is readable. When the patch is removed, part of that modification still exists and the phone is unable to determine its IMEI - so it reverts to a factory default IMEI, the "0049" number.