I haven't worked on anything that needed a 30-year product life, but I have worked on products that went into semiconductor manufacturing equipment, and needed 10+ years of support.
At least in those cases our customer was sane enough to realize that sometimes a slight redesign is the most cost effective and reliable solution.
Not every semiconductor manufacturer does lifetime buy notifications by package
Every reputable semiconductor manufacturer will give notifications on a per-part-number basis. If there is a manufacturer out there who doesn't do this, I wouldn't purchase from them for any project, let alone one with your stringent support requirements.
Reputable manufacturers don't just notify if a part/package is going obsolete, they notify for any change in the product that might impact quality (in the ISO 9000 sense). For example, they notify if the lead finish is changing from tin-lead to matte tin. They notify if the device packaging process is being moved from one factory to another.
some manufacturers simply fold up and disappear
This, or course can't be helped. And there are other similar risks.
David mentioned a case where a factory fire resulted in product obsolesences without notice. In another recent case I know, a (large and extremely well-known) fabless semiconductor company was forced to obsolete several lines of products because their foundry vendor decided to close down an older (and no longer sufficiently profitable) manufacturing line. At least in this case they were able to give advanced notice and allow for lifetime buys...but their products were not $0.05 transistors, they were complex $20 - $200 ICs, so you can imagine the investment required for some lifetime buys.
Other risks -- regulation
One more thing to watch out for is the march of environmental regulation. The European RoHS directive and similar laws may not apply to your products, but they affect your supply chain. RoHS, for example, forced a lot of mature products to be redesigned, reducing sales volume for a lot of mature components, which probably resulted in some obsolesences as specific parts became unprofitable.
New versions of RoHS are expected within a few years. So you can expect a new wave of obsolesences as the market settles out in relation to the new rules.
Other risks -- changed market landscape
If you designed a product 30 years ago and you designed it entirely with multi-sourced components like 2N2904's and 74LS04's, you would very likely still be able to get all those parts today.
But the trend in the last many years is away from multi-sourced components. Very few new products are being replicated across manufacturers. And the parts that are are at similar complexity levels to what was available 30 years ago --- hex logic gates, individual transistors, etc. Even "simple" devices like linear power regulators are now complex enough that nobody tries to duplicate another company's design exactly.
If you want to design in a microprocessor or a programmable logic device, you are simply stuck with a single-source component, and all the risk for long term support that entails.
Also, as my anecdote above pointed out, the rise of the fabless semiconductor company also adds risk because it means your chip vendors may not actually control their own manufacturing resources.
To me, it sounds as if your sales team needs to get tougher with this customer (of course, engineers always say this).
One option is tell them you can fix the problem their way, but to maintain this level of support, the product price will be increasing XX% each year for the remainder of the product lifetime. You can make a lifetime buy for these obsolete products, but you'll need to pay for engineering evaluation of the requirements, technicians to manage the inventoried parts, etc., and you need revenue from these products to support that.
Another is to call their bluff on the re-tender process --- there can't be that many competitors out there who could realistically support these lifetime requirements, and those that can will price accordingly. On top of that, your team has experience with this particular application and the customer's detailed requirements, giving you an advantage when it comes to bidding the project. Who knows, you could come out of a re-tender with a contract at a substantially higher sales price.
As others have said, it is difficult to see redundant ALU logic within a core.
A core was designed to optimize throughput. Any additional logic for a redundant ALU would impact performance and increased area would slow down the whole core. As technology evolved, the silicon became smaller, making cores faster, but essentially using the same intellectual property. Why have redundant ALU's, when space is available for redundant cores to increase production yields?
In 2011, Intel filed a patent for at least 32 cores with 16 active and 16 spare. The patent states failing cores would have higher temperatures allowing a spare core to be switched in. Essentially, dynamic core allocation as required.
You could have high-power and low-power cores allocated as required by tasks. Or switch out a bad core detected by higher temperature levels. Operate the cores in a checkerboard manner to reduce heat.
Intel Patent: Enhancing Reliability of a Many-Core Processor