It's been well documented that K2 had given Valuev SEVERAL offers to fight, and indications are that Valuev was willing to take them (at least the last offer), however DK and Sauerland always priced him out and kept him away from K2 at all costs.
King never wanted his guys to defend against a Klitschko. He had no control over them since he missed signing them (there was a hilarious scene in the Klitschko documentary where King fakes playing a piano and Vitali notices during the recruitment process) and didn't want to risk losing a belt to them. That's also why the Brewster rematch didn't happen until after he'd lost his belt to Liakhovic despite Wlad pursuing it sooner. Lamon was a warrior and would've agreed to an earlier rematch, but King was in the way.
I actually had hopes once that Vitali vs. Valuev would come off in 2010/2011 but as everybody says, negotiations didn't ever work out despite whispers that they had happened multiple times.
I think Vitali and Valuev even met in Germany to discuss a fight it is clear Valuev wanted it to happen but King wasn't willing to risk the belt. Would have been an interesting fight and for unification.
I looked it up, apparently it was in St. Petersburg. Note Valuev's slick attire, dressed to impress http://i.imgur.com/B4EP7gh.png
I don't think Valuev avoided him, I was more a Don King choice: King was tired of his fighters losing to Klitschkos. Don only agreed to the Haye fight because he had signed a 2 fight option with Haye and viewed Haye as a minimal risk.