Well, one thing I noticed is if I am on WiFi or with data on, I tend to find my phone. Microsoft uses three different methods, I believe, to find your phone. One is using the location caching sent from your phone regularly if you have that on in the setting. The other is sending an SMS to force your phone to send a location, in which case your carrier needs to support global SMS I believe, and lastly, they send an email to do the same thing the SMS intended to do.
So first thing you should do is to check whether both boxes are checked in find my phone in settings. Secondly, be patient, if Microsoft can't locate it right away, they will send you an email when they do find it.