Do they really qualify as being "new" every time they rebrand MSN Search? That seems overly generous to me. Google rolls out updates all the time too; they just got the branding right the first time.
"Bing! The NEW search engine". Not a mention that it's a rebrand of a crappy microsoft search.