Andrew,
As Okechkwu says, you can actually do the unlocking yourself. But your iPhone must be on a supported baseband. Most iPhone 3GS phones would be supported by upgrading to the 'iPad' 0.6.15 baseband and unlocking. For iPhone 4, if you are on the old baseband, you should. Both iPhone 4S and 5 don't support unlocks for now.
Earlier, they are some members here who offered 'Official Apple Unlock'. You could also try them out.
Anyway, the rule of thumb with buying new iPhones, just go for unlocked from Apple Store. don't buy from carriers such as AT&T or even Orange KE. Cost tends to be the same with locked ones.