But given that one of the problems with the (iOS) App Store is finding products in the first place (niche products can easily be buried by popular ones), the idea does have merit providing the companies are prepared to be altruistic. It wouldn't be very helpful if Bing only returned Windows Phone 7 apps, for example.
And if they were going to do it for mobile apps, why not include desktop software too? Admittedly there's less chance that there would be a program that corresponds to a search request, but there are examples. For instance, someone using a Mac to search for "weather forecast australia" might benefit from seeing links to TheBOM Weather Widget and similar pieces of software.