You can't redirect (3xx) and signal a client error (4xx).

I don't know what you mean by "giving the search engines the correct info.", so I can't suggest a solution.