They should replace their logo with a big black rectangle. This would get everyone's attention (not just google.com visitors).

They don't need to commit commercial suicide by shutting off their site ('hey, bing isn't that bad..'), but this is pretty weak.