Can't say much about Android, but the Back button on the Windows Phone is unreliable and doesn't always take you back to where it's supposed to be. It's just confusing. I much prefer the simple UI that iPhone has with a single button.
The problem here, I think, isn't so much the button itself, but developers not following the conventions, and Microsoft (and possibly google, I don't have an android) not steering developers in the right direction.
For example, the IMDB app on WP7 has a search icon on the top right of the screen which they expect you to use to search. They should have used the already existing search button on the phone, but if you hit the phones search button, you go to bing search, because the app only knows how to use it's own search button.
Same with back buttons. If the developer has used it properly, it should take you to the previous screen of that app, but 90% of the time, it goes to the previous app.
Hopefully 'app switching' in mango (I don't think multi-tasking is the problem, its that we can't switch from one app to another without going to the home screen) will solve much of the back button issues, and possibly the new Bing/app search integration tools will help with the search button.
Personally, I just don't see the usefulness of Back buttons on WP. The Back button should be replaced when the multitask swtich feature in "Mango". The Search, maybe, it's useful sometimes. Again, like you've mentioned, the users would have to guess whether it will bring up the Bing Search or the in-app one. It sounds just confusing.
So you would remove the back button in web browsers, right?
FF1 http://en.wikipedia.org/wiki/File:Firefox_1_0_8.png
FF5 http://en.wikipedia.org/wiki/File:Firefox5.png
Remember Netscape? http://en.wikipedia.org/wiki/File:Netscape_Navigator.png
I can clearly see the back button in all 3 UI pictures, including the one for Firefox 5. For that matter, I can see the back button in the Firefox 5 window I'm using to type this comment. I agree that Firefox 5's UI is simpler and cleaner than Firefox 1's and Netscape's, but I don't know where you got the idea that they'd eliminated the back button.
btw, IMDB can't support the search button because it's actually not exposed to third-party developers. Use of the search button for in-app search is actually scrapped in Mango because people found it confusing - the built-in apps that support search now have their own on-screen search buttons.
I guess that is really the problem, the majority of apps follow convention, but then every once in a while you get something that doesn't and it is gets confusing.
Having fewer buttons seem to make interface cleaner and less chance to screw up for users. But again it's a hardware issue for debate rather than software.