Thanks for your suggestion Aleister. I tried using ‘init’ as the hook for my action, but it was rather difficult to check if the request triggerd a 404, especially since is_404() isn’t defined yet at that point.
What I did find out, is that it does work with the hook ‘template_redirect’. It appears the server hasn’t send any output to the browser yet so I can still send a 301 header.
I’ll post the result soon.