How can I serve a "410 Gone" HTTP status AND redirect my removed content?
You can always output HTTP 410 header and redirect human users using JavaScript in a body:

var delay = 10000; //Your delay in milliseconds
setTimeout(function(){ window.location = URL; }, delay);


JavaScript from this answer.

Note that by rfc2616:


  The 4xx class of status code is intended for cases in which the client seems to have erred. Except when responding to a HEAD request, the server SHOULD include an entity containing an explanation of the error situation, and whether it is a temporary or permanent condition. These status codes are applicable to any request method. User agents SHOULD display any included entity to the user.


Emphasis mine. So, JavaScript outputted inside HTML body should work. But of course it is not guaranteed it will.

Your content is not nodes, so you probably have implemented hook_menu. If not, you can alter existing implementation with hook_menu_alter. What you need is to:


Using access callback and/or access arguments, ensure user gets the access permission to deleted content. If not, he will see 403 or 404, as this is Drupal's default behaviour for unpublished / deleted data.
In page callback test if content is valid, deleted or never existed.


If valid, default to the callback you are using now.
If deleted, use drupal_add_http_header to add "410 gone" header as appropriate. Output nice human readable page (optionally with JavaScript redirect, search box or anything appropriate).
If never existed, either default to what you were using already, or implement 404 the way you implemented 410 above.





Google says:


  We recommend that you always return a 404 (Not found) or a 410 (Gone) response code in response to a request for a non-existing page.