I think you have a problem understanding the HTTP protocol.
Imagine you knock on a door and ask for a photo of a certain teddy bear. This is a HTTP request. Now, you could get some different responses:
|Human behind the door||Status Code||Status Text from RFC 2616||Notes|
|"OK, here you are", and hands over a pretty image||200||OK|
|"Do you want a picture of it in the green shorts? Or with the new stylish jeans? Or in the fluffy dress? Or ..."||300||Multiple Choices|
|"Sorry, I gave the teddy to the son of my neighboor just over the street. Ask him."||301||Moved Permanently||Note that you will never see the teddy bear here again.|
|"Hmm, let me think. Where did I put it? Hmmm... - Oh right, it's at the neighboor next door."||302||Found||No information about how long the teddy bear will stay there.|
|"Walk around the house, I'll give it to you through the front door"||303||See Other||RFC: For redirects from POST to GET|
|"Oh, right, that teddy bear. My son has carried it into the basement, go there and ask him".||307||Temporary Redirect||The teddy will come back here.|
|"┐Hablas espa˝ol? Parlez-vous franšais? Sprechen Sie deutsch?"||400||Bad Request|
|"Let me see your ID card first, please"||401||Unauthorized|
|"Hand over the money first"||402||Payment Required||No, I'm not kidding. But as no one has a working concept for payments inside HTTP, the code description has changed to "reserved for future use".|
|"YOU, Sir, won't get that from me."||403||Forbidden|
|"I don't have no stinkin' bears."||404||Not Found||Not here, no information if it was here before or will be here later.|
|"The bear photographer? No, he doesn't live here any more. Don't know where he's gone."||410||Gone||Gone, and won't come back, like 301. But no new URL known, so no redirection.|
|***KABOOOOOM***||500||Internal Server Error|
|"Sorry, I don't have a polaroid."||501||Not Implemented|
|"My parents are not at home. Please come back later!"||504||Service Unavailable|
Is it clear now?
What answer do you want to give? 404 means "I don't have that, and I don't know where it is." No Redirection. 301/302/303/307 means "OK, I don't have it here, but look over there." with minor differences in WHY you don't have the requested resource. Redirection follows automatically. Or the really hard 410? "It is no longer here, and it won't come back."
Why do you think that search engines or customers need a special treatment? If a resource is not available, send 404 or perhaps 410. If it is elsewhere, send 301/302/303/307.
If you want to help humans navigating your page when they hit a 404 page, you could add a search form, a link to a search page, a link to a site map, or links to the most wanted pages to the 404 page. Just make sure that the 404 page is larger than 1024 bytes, or else MS IE users will only see a braindead default page generated by the MS IE.
Today I will gladly share my knowledge and experience, for there are no sweeter words than "I told you so". ;-)