I also have English OS, Firefox using English locale, and I am in the US.
So to force me to use Japanese map service, I went to www.bing.co.jp (same as I do for Google when I explicitly want Japanese results), the select Maps from the top menu. Since you are in Japan, Bing might be sending you there by default.
Then I entered "10 Downing Street, London" as you did. Well, it could not find it.
What I finally figured out is that you have to enter the search location in katakana as it is shown on the map. Not there, no dice.
In UK and US maps, zooming in there are cities in alpha text, but search could not find them. I think if you can find "10 Downing Street" by going there on the map manually you will see what you can search for (as long as it is in katakana). Kind of backwards though.
EDIT - Additional Information:
Based on OP's feedback, he could go to a national Bing site you would expect to be in English (in this case www.bing.co.uk was tried), and the maps were in English again. Then (again from Japan) maps on www.bing.com also were in English, probably due to a cookie being set.