I would suggest that you use routes.

Most of the time I think it's easier for you to determine your rules by code than to setup handlers in config.

If this is an existing solution, you should also have SEO in mind - old urls should return 301 Moved Permanently.

It is an existing site, so you are right Mari it should return a 301 moved permanently. 

Any suggestions on which approach to take? Is HttpHandler the correct way then?

It may be that you could use Rewrite Module for IIS - a rewrite can be setup with type permanent, see:

http://www.iis.net/learn/extensions/url-rewrite-module/creating-rewrite-rules-for-the-url-rewrite-module
http://www.make-awesome.com/2010/03/301-redirects-with-iis7-rewrite-module/

You could also use the 404 module - see https://www.coderesort.com/p/epicode/wiki/404Handler

The module supports xml import of redirect rules in format:

<redirects>
   <urls>
       <url>
           <old>/templates/page.aspx?id=1234</old>
           <new>/travel</new>
       </url>
       <url>
...

Thank you for the suggestions.

We are already using the 404-module, but in this case it is more than 1000 URLS that we need to remap, so I am not so keen on the xml import approach due to the risk of errors happening (typing). Additionally, I already got some code in place that can parse the old URL into an object, which should make it easier to map into the new URL.

I ended up just adding a route and implemented an IRouteHandler, like:

RouteTable.Routes.Add("ROUTENAME", new Route("ROUTEURL", new IRouteHandlerImpl));

Where

ROUTENAME = name of route

ROUTEURL = url-pattern to match

new IRouteHandlerImpl = implementation of the interface IRouteHandler