A little while ago I had a problem where a client I was working on kept failing to locate the site.
Normally when you get an error like this you tend to find there are missing tabs and maybe a missing site code etc. The location services log file was saying that there was no infomation being returned from the MP, yet as you can see from the image above everything looked otherwise intact.
When the client was installed, a Fallback Status Point was specified. A Fallback Status Point was installed on the primary site but it transpires that this isn’t enabled by default (at least it wasn’t in my case). Once this was enabled everything began working again.