How can large websites cope with 1000's of old web addresses which are erased everyday? specially when the web site redirects to some personalized error page on striking a damaged url rather than tossing a 404 error page. (I have read internet search engine spiders don't consider web addresses that throw 404 error page)

If your page is erased, I'd highly recommend that you simply build your "personalized error page" really return a "410 Gone" HTTP header.