Sorry to hijack the thread but it seems like people have a slightly different but related problem here
You need to have some proof of purchase. Think of anything that you can produce before them. Any records pointing to the fact that you, the customer, is linked to your phone, the product.
If you bought it online then any mail, confirmation of purchase, acknowledgement... you'll have to look for whatever evidence you can get hold of. If nothing else, then just be careful with your current phone at least. Keep the bill. Well, request for the bill in the first place. Install apps that I talked about. Prepare for possible scenarios where you can trace your phone. Try all features of app and DO perform a dry run (see if you can locate the phone by yourself at home)
Truth is, without the right documents or acquaintances it is an Indiana Jones affair