The search engine could ignore all takedowns and be in exactly the same situation as it would be without the DMCA; the safe harbor provision isn't a mandate on them, it is a benefit to them. They deal with takedowns because the cost of doing so is less than the cost of copyright liability they would have without the DMCA, which means the DMCA is saving them money, not imposing a cost.
You're treating the safe harbor and notice and takedown as indivisible when they obviously aren't. Conditioning the safe harbor on notice and takedown is a huge cost compared to the alternative used in CDA 230.
They obviously are both part of the DMCA, so you can't say that the DMCA imposes costs based on the notice and takedown condition for the safe harbor, because ignoring that condition leaves the host in the same position they would be in without the DMCA.
You can say that the notice and takedown requirement reduces the cost savings of the safe harbor compared to the hypothetical policy of an unconditional safe harbor, or one with alternative sets of conditions, but that's a very different claim than the DMCA imposing costs.
The safe harbor and the anti-circumvention rules are both part of the DMCA too, but it's silly to argue that the anti-circumvention rules don't impose net costs because if you average them together with the safe harbor it comes out somewhere near neutral. They don't cease to be divisible just because they were enacted at the same time. Otherwise you could justify anything by just finding something which is as good as the target thing is bad and lumping them together on the same side of the scale.
And if you've never gotten a DMCA takedown from Perfect 10, you probably don't understand the true terror of the DMCA process.
The problem is that the shield has value to the search engine in excess of the cost to the search engine (but not the cost to the censorship victim) of removing the information. It reduces their risk, even when the risk is low because they would be likely to win, and removes the cost of having to litigate the issue even if they do win, so the search engine takes the deal and then executes ~all the notices even when they're bogus.
Which is a direct cost to the censorship victim compared to handling it the way Section 230 does it, and an indirect cost to the search engine because it has them paying to process the removal of legitimate information and reduces the value of their service to customers -- just not enough of an indirect cost to give them the incentive to refuse, because the brunt of the cost is on the third party being censored.