I'm not the most knowledgeable within mobile geekery, but couldn't you in buy an android phone with no contract over the net and get a sim card for it?
The point regarding IMEIs was that if carriers get antagonistic enough, it would be possible to change the blacklist that (some) carriers use for stolen phones into a whitelist that disallows any third party phones.
Outside the US, governments take the promise of being able to take a SIM and put it into an unlocked phone very seriously, so I'd say this is a strictly local problem. In fact, I'd wonder how Deutsche Telekom's regulators would react if T-Mobile (DT's US subsidiary, at least for now) started doing something like this (that they probably wouldn't permit in Germany).