Did you test the redirect using a test user or as your admin account? The admin would have access to the deleted topic so would land on that, but a regular user should follow the redirect you’ve set up in permalinks.
Hmm… Couldn’t get it to work… But then I found out something strange - it seems that Chrome caches redirects? Because when I changed browser then it seems to work… investigating some more…
OK! Figured it out.
If the topic is in a private / non-public category, then redirects seem to be “stopped”. When I moved the deleted topic back to the public category and deleted it from there, then redirect worked…