There is also the psychological factor to consider. Google is perceived as the industry leader of search engines, and this has been true for a long time.
The mere fact that Google has become a verb speaks volumes as well. Look at the parallels in other industries; we don't "send" an overnight package, we "FedEx" it. In that same manner Google equals online searching -- we don't "search online," we just "Google."
Regardless of the improvements and optimizations Bing may develop, winning over the user who is used to "Googling" will be a huge, huge challenge for Bing. Their TV ads, while clever, will not do it.
I don't see that as too much of a factor. I say "searching online" all the time and to be honest the only people who are unable to separate the different actions in my experience are very old or inexperienced internet users.
I think the real difficulty will be making a search engine that is so much better than Google at finding what you want that users will be willing to go out of their way to use an alternative search engine in combination with their Gmail/YouTube account, Chrome browser, Android operating system and variety of other Google products that are bound to keep coming out.