Bing's released business data sets are currently limited to several countries (with the exception of Hotels, which are global, as you have cleverly observed). On Windows Phone, if your settings are outside of the "Bing powered" markets, your results are actually powered by Nokia behind the scenes (I just tested and it even says "results by Nokia" on the local pivot when searching with the hardware search button). My team actually built the service making it easy for the WP team to leverage the Nokia partnership and fill this coverage gap (NOTE: This is different than the Nokia Map app on the Nokia 920 phone. You are using a Windows Phone native app, but powered by Nokia search under the hood.). We are working as fast as possible to expand Bing powered coverage for all Bing entry points with a high quality experience, but no ETA to announce by me.
Dr. Sven, when you get to MS, I can hook you up with some dogfood and a feedback alias since you are familiar with several regions worldwide.