We just released the new version of 404 handler which is hundreds of times faster than previous versions.
You can install the new package from the Package Manager Console using Episerver NuGet Feed.
For CMS 11:
Install-Package BVN.404Handler -Version 11.2.1
For CMS 10:
Install-Package BVN.404Handler -Version 10.4.1
The latest version requires migration of stored redirects. After installing the package, you should open administration screen in the redirects gadget and head over to "Migrate redirects from DDS to SQL." Then click on the "Migrate" button. After some time (depends on the redirect count), you will see a message telling how many redirects were migrated.