SIM lock removal requirements imposed by different GSM providers in the US:
AT&T Wireless (now merged with Cingular): Will not remove a SIM lock from your phone for any reason. The Terms and Conditions of AT&T Wireless (and Cingular) state this - though they are very vague (and I quote): "...if your Device utilizes a SIM card it will only accept a SIM card provided by us...". This seems to indicate that the phone was made specifically for AT&T Wireless or Cingular. But a few of their phones are also available from T-Mobile.
T-Mobile: After 90 days of active service, T-Mobile will remove a SIM lock. You just call or send an e-mail containing your subscription and phone information and they'll send you a code to disable the SIM lock. By far, T-Mobile is less restrictive than most providers.
From this, it appears that the only GSM-based provider that removes a SIM lock from their phones is T-Mobile (and then only after 90 days of continuous service).