Not possible on most iPhones. It is possible on the iPhone 2G since the baseband was completely cracked. It's also possible on other phones where the signature checks can be bypassed
I'm under the impression that the CDMA carriers already block phones that are reported as stolen. For some reason the GSM carriers don't, though it looks like they will be required to do so soon enough.
Carriers can't do much about international sales. Apple can since the iPhone phones home every time it activates.