I bought a used iPhone 4 with iOS 7 from a local shop. I am not sure as to how to be sure if it is not stolen. I was able to do a factory reset on the phone and use my own Apple ID to use the phone.
I tried going to iCloud to check if Find My iPhone was active on the device and I found out that it is activated but using my Apple ID only.
I know that I should do a proper verification before I bought it but I think it is too late now and nothing can be done about it other than checking next time I buy a used phone.
As proof of purchase the store owner wrote the Price on a Plain paper with his name and phone number and handed it to me.