I think to avoid fakes the best bet would be to buy a locked phone from a private seller. It is very unlikely that any large GSM carrier will provide fakes on its contracts.

Then you can either get a free pay-as-you-go SIM card or ask the seller to get a free SIM card for you and send it along with the phone and unlock the phone for a small fee.