They are already bringing in outside consultants from McKinsey, but in this day and age, how about turning to the crowd for help? If they posted significant cash prices (say $1m total) and let their users vote on the best ideas, I bet they could find some fresh directions.
Also bet it would cost a fraction of what they pay McKinsey.
Edit: In fact, why stop there. How about making it a quarterly challenge. With follow-ups on what ideas they decided to work on and progress reports. Make Yahoo the People's company. Just my 2 cents.