Last year, Andreessen Horowitz was invited in to take a deep look at Yahoo and decide if they wanted to be part of a syndicate to buy it outright.

Those conversations then switched to the possibility of taking an active minority stake. And then the Yahoo board, in all of its brilliance, decided to hire Scott Thompson and an army of consultants from Boston Consulting Group to save the company instead.

That didn’t go well.

As reported today, the board has made a remarkably different choice with Thompson’s successor: Former Google executive Marissa Mayer.

I caught up with Marc Andreessen and asked if he, as someone who has taken a deeper look at the company than most, thought Mayer could pull it off. His answer spoke volumes about the sudden and dramatic repair in goodwill the company has achieved, simply by naming Mayer as CEO.

“If you had asked me a week ago [if Yahoo could turn things around] I would have said, ‘No way. It’s too late. It can’t be done. The neglect has gone on too long,’” Andreessen says. “On the other hand, I would have also told you there’s no way that Marissa would be available. She gets recruited all the time and has a pretty big job at Google. So the fact that she is available changes the scope of what might be possible.”

Why so much enthusiasm? Other than founder Jerry Yang, there is almost no one on the planet as well suited to step in and immediately start making things better, Andreessen argues. In fact, you could argue she’s even more qualified than Yang. She has distinguished herself in pretty much the exact same business, and watched Yahoo closely as a competitor. No one has to explain online advertising or mail to her, he says in a not-so-subtle dig at Carol Bartz. “At least she’s not going to be surprised,” Andreessen says.

Expectations are so high, in fact, that he argued that taking the job was a no-lose proposition for Mayer personally.  (As stated earlier, I don’t quite see it that way…) If she pulls it off, she’s a genius. If she fails, not even Marissa Mayer could save the company, he says. I’m not convinced she’d escape so unscathed, but it’d be hard for her to perform worse that her predecessors. Part of this is the changing nature of what “risk” is at this level. “In the old days, risk was I lose my job, house, or career,” he says. “Now risk is ‘Let me tell you stories of how badly that went.’”

In fact, that level of confidence causes a new problem that Yahoo hasn’t had in a long, long time: Expectations that may be too high after today. Andreessen says if he was in the job he’d work hard over the next six months to plant stories about just how bad things at Yahoo are — just to dampen all that enthusiasm.

All of this Mayer-boosting aside, it may still be too late to fix Yahoo. But Andreessen says the one thing he’s watching for is how big of a staff cut Mayer is willing to make, quickly. That was the big take-away from when he looked at buying the company. Yahoo is just outrageously bloated and, practically, it means you can’t get anything done because “25 people are in the room for every meeting and everyone weighs in,” he says.

Yahoo has 18,000 employees, and on paper it should have closer to 6,000 to 8,000, Andreessen argues. Every analyst has noted pretty much the same thing, and to date no CEO has had the guts to cut that deeply, even as each of them have been vilified for making cuts. Will Mayer be able to do what most outside observers say is necessary?

This single decision will telegraph three things that are all central questions for a Yahoo under Mayer: How big of a bet is she making on the people there versus outsiders? How much does she expect to grow the company organically versus by acquisition? And is she willing to free up the company’s cash for aggressive investment in new areas?

All the reasons to dread taking a job like this are well documented. But traffic, a global sales force operating at a huge scale, loads of cash, and a huge global datacenter operation are four assets that Yahoo still has — brand damage and staff exodus aside. Beleaguered giants like RIM and Nokia certainly don’t have those advantages, particularly the cash. The other three are assets that only a handful of companies have — one of them being the company Mayer just came from, another being the sexy, newly public Facebook.

Theoretically, Mayer could take marginally profitable sites and plug them into that matrix, Andreessen says. Those sites could become hugely profitable instantly by Yahoo flooding them with traffic, its sales team selling ads on steroids, and their data centers taking out massive costs on the back end. He compares it to what Cisco did with its spree networking mergers and acquisitions, and I’d draw an analogy to Oracle’s $20 billion roll up of once-hot-but-still-profitable enterprise software applications.

Of course, the Valley is full of such theoretical acquisitions that wind up failing in actual practice. As someone who came from the AOL/TechCrunch mess, consider me skeptical.

So was Mayer crazy to take the job? Andreessen wouldn’t answer, hedging “It’ll be interesting.” (Oh, media training…) Either way, this is a three-to-five year job, and he assumes Mayer was given a promise that she’ll have that long from the board.

So, yes, this will be interesting to watch. Either it will represent the final end to any shred of hope that Yahoo can be saved or one of the most stunning turnarounds in the tech industry’s history — the likes of which we can count on one hand.