I switched the api from Bing to Google Maps. The api is a lot easier to use and it gave me the right results.
With Bing I had a 9/10 change to get a "Not_found" error, tested with the SAME address! So sometimes it works (1/10 chance). With Google I get a correct result on each try...
Don't make the same mistake as I did, if you want to lookup address in another language than english then use Google Maps API.