Your IMEI (phone id) and IMSI (simcard id) are recorded when your device picks up a base station or wireless hotspot. The only people with these databases outside of the security services are the network providers in that country that the device is being used in. Any company on the internet purporting to locate your phone via IMEI are calling off the internationel barred imei database which is effectively useless to you.
Speak to the network provider initially. Report your device to the security services and report it on in country lost property sites. Loads are available for free. Pawn shops and police check these frequently.