They are not fickle. They are ignorant. If you had access to as many log files as some of us do you would know that users make no sense when they search. I had one site that got lots of visits from people typeing in distance to country. Where country was whatever country they wanted to know the current distance to. Do you know how many people type in www.domain.com and then go wow G is so great it found the site I was looking for. The amount of users that really care about how good a SE really is and would switch would not even beat out ASk.com.
If you know anything about marketing you know that all you have to do is be number one and stay there long enough to have mindshare. All you have to do to stay is to not take away what they are used to. Don't give all the old netscape examples they are not relavant. The internet is at a place now where the avg person usees it. It was not back then. G has hit a critcal mass. MS should be number one it is the first thing anybody sees on their computer. They have to look at MSN search and then type in www.google.com.