BingRestMapProvider always search with Structured URL and that is why it fails to find locations via long query search strings like: 

"royalton rd & brecksville rd brecksville oh"

You can see the difference between Structured and Unstructured rest search URLs here:

https://msdn.microsoft.com/en-us/library/ff701711.aspx



As a workaround, users can override BingRestMapProvider like so:

 public class CustomBingRestProvider : BingRestMapProvider
    {    
        protected override Uri BuildSearchLocationRequestUri(BingRestSearchLocationRequest request)
        {
            Uri baseUri = base.BuildSearchLocationRequestUri(request);

            string newPath = baseUri.AbsoluteUri.Replace("Locations/", "Locations/?q=");

            return new Uri(newPath); ;
        }