You can try searching for "unlocked cellular phones". These phones are not locked into any specific carrier. Unfortunately unlocked phones generally cost more because of what atom said.
Also, you should make sure that your carrier will work with the phone because different carriers may use different protocols and frequencies. In my area, all Nokia models that end in 60 (5160, 6160, 8860, etc) only work with AT&T.