I genuinely tried Bing when it first came out but it didn't stick. I have been using DuckDuckGo for a few weeks now and I have changed all my default search engines to it. Great features (! search and zero click info, not to mention not storing my search information).

Like you mentioned, Gmail on the other hand is much more difficult to drop. I spent half hour going through http://news.ycombinator.com/item?id=1121269 looking for a decent solution.