I can see couple of options for an approach to solving this issue:
URLRewriting
One possibility is to rewrite URLs (similar to mod_rewrite) to convert them from format that is imposed on you into a format that MVC can route natively. There is an IIS Module from Microsoft that does just that, and I believe (though not certain) would have the necessary functionality to accomplish the task in your case. The basic principle here is that if the format cannot be handled by MVC due to route template parsing rules, then convert the URL to something that it can manage before it even reaches the MVC route handling. URL Rewrite is an IIS Module that sits before MVC handler, examines the requests, and is able to rewrite the request from one form into another. Then, this altered form is what is seen by MVC and can be understood and parsed by it. E.g. the URL of /1234-hello-kitty
can be rewritten by the module as /1234/hello-kitty
and then MVC route template would be a simple {noteId}/{*title}
. The downside caveat here is that generating links may not work here since generated links would look like /1234/hello-kitty
rather than /1234-hello-kitty
. However, mitigation may be to have a route specifically for link generation and not for routing defined as {noteId}-{title}
. I believe (should be verified) that this will actually generate a link in form /1234-hello-kitty
(albeit not being able to parse it on incoming request).
Custom MVC route handler
This one basically draws on the idea that if MVC doesn't do it for you, override its behavior to do what you wish it would do. The tactical aspect of this is described in SO post on how to provide your own handler. The way you would use it is you can provide your own interpretation of parsing of segments of url to route data, and provide the actual values as you parse them into requestContext.RouteData.Values["nodeId"] = /* your code that gets noteId out of URL. */
. The rest of the application works as any other, knowing nothing about this surgical intervention in routing.