It surprises me that Google gave up so easily! This is a pretty similar service to what WebMynd provides - we're handling ~2.5m pages per day and although scaling is difficult, it's doable.
We out-engineered Google!!
We out-engineered Google!!
The problem Google is having isn't with storing the links, its with the effect of the links on the personalization of your search results. Which is a problem WebMynd isn't facing.
They can't precompute the eigenvectors because it changes every time you visit a web page and calculating it live for each search request when the user has thousands of personal pages can be expensive.
I would have just disabled the effect of the personalization on search of bookmarks not added manually.
However, I would point out that WebMynd IS doing personalised search (totally personalised, in fact). As you point out, updating search indices every time a user visits a page is difficult. The fact that Google have chosen not to tackle this challenge, and we have, is a symptom of their existing methods and stated goal of organising the world's information: not your's.
As for your last point, I actually agree with the OP and others that Google's soft touch on this matter was commendable; disabling the effect or blocking the extension outright would have been heavy handed and sent a pretty bad message.
I think that requiring a deliberate, conscious vote of confidence from the user for a web-page before actually letting it affect my personalized search results is a very good thing.
But from a public relations POV you're probably right, that was the best approach
I hear they're hiring also, if you want to help them out-scale Google!