As others have noted departures at this level are always much more nuanced than simply "this was bad" or "this was good." None of the departures where I was pretty close to the departee and the situation were 'unexpected' in the sense that their course had a way point which usually pointed 'up' or 'out'.
So think about your own career, think about what you want to do, what mark you want to make on the world, what things are you passionate about. Sometimes a company changes direction, from market forces or personnel changes and the company and the individual become less aligned. Its always possible to see if you can bring the company back toward alignment, it's also possible to see the cost or probability of that happening.
In my own experience I was a VP level technical contributor at a company during the dot.com boom. I arrived as part of an acquisition which was pushed by the CTO of that company who had a vision for a richer services oriented IP connectivity solution for multi-tenant buildings. A series of missteps, some poor 'chemistry' between the executive team, and a general collapse of the DSL market, made it clear that even though I had an employment contract with these folks, the place they were going (back to their 'roots' as a wiring solution) wasn't a place I would find very interesting. I talked with the CEO, we looked at all the options, and both agreed that the 'right' answer was going to be for me to leave. That didn't particularly bother me, because the parting wasn't really a reflection on my ability or non-ability, things had changed I had a choice, I chose not to follow that change.
Contrasting that for when I left Sun (certainly not as senior level as that) where I had poured a lot of energy into the product that would become Java with visions of building really strong capability based systems and light weight task specific operating systems, only to realize that Sun 'corporate' had decided that Java was the battering ram to try and deflect the Microsoft Juggernaut of Windows/NT and a growing Enterprise presence. I was really pissed off. I talked to Scott about it, Eric Schmidt (CTO at the time), and James Gosling. To their credit everyone was very supportive of my passion but in the end the company gets to decide what they are going to do with your work product, and I could not get Sun Labs to sponsor my secure version of Java and while I felt e-commerce was going to define the killer App, realistically in 1995 I was about 7 years too early to that particular party. So, just about 3 months shy of getting my 10 year pin/clock/whatever I stormed out. Emotionally I felt pretty liberated, feeling like Sun was too clueless trying to protect their enterprise accounts to see the low hanging fruit right above them.
The only place I have felt truly bad about leaving was Google, not because I was leaving, it was clear to me that Google and I had incompatible goals, but because I felt like I had failed the folks who were fighting the good fight and I left them there to suffer. The path to success there was pretty clearly laid out for those who looked for it, but the cost for me was high, too high.
Its really great of you to stand up to what you believe and go that way. I think that's the reason why you are the VP of blekko now.
Any advice to young folks like us, who dream to make it big some day?
P.S: Read your HN profile just today, although i've been reading your comments and replying to them for a while on HN. But that's the beauty of HN isn't it?
I am a firm believer though in three fairly general things; follow your passion so that you don't find yourself regretting today what you didn't do yesterday, seek out contrary views to help you understand your own ideas, and choose not to take things personally. Doing that won't necessarily make you popular or successful but they will let you stay centered and happy with yourself.
However, it was a company and there were people who put in effort day in and day out that kept things working, people that were indispensable to day to day operations of the company, who were not getting the recognition that folks who would create a solution to a problem nobody had were getting. These unheralded people were 'fighting the good fight' and I worked pretty hard to wake up HR to that oversight on their part. They had just started giving out 'infrastructure awards' as a way of recognizing those folks when I was leaving. I was glad for that. I didn't get a chance to work on one of the committees that evaluated that sort of work which was too bad. Given the changes I've read about since I left it would seem that the company has shifted away from some of that stuff.
To give you an example of how sad a case I was, when I came to the Bay Area I had offers from Xerox and Intel and was totally excited to go work at Intel because they were shipping the products that were changing the world. My wife worked at Xerox and so I got to see a company that could envision an amazing future, and not ship it, and even then I knew it would drive me insane not to get things out the door :-).