When you set up a content route it will be set up with a starting point of the route. By default it will start routing from RootPage. It is possible to define another start point as in example below where start page is set as start point for the route:

var urlSegmentRouter = ServiceLocator.Current.GetInstance<IUrlSegmentRouter>();
urlSegmentRouter.RootResolver = sd => sd.StartPage;
var parameters = new MapContentRouteParameters
{
    UrlSegmentRouter = urlSegmentRouter,
    Direction = SupportedDirection.Incoming,
    Constraints = new { company = @"\d{8}", node = new ContentTypeConstraint<SelfServiceBasePage>() }
};

routes.MapContentRoute(
    "selfservice",
    "SE{company}/{node}/{partial}/{action}",
    new { action = "index" },
    parameters);

Hey Johan, thanks for the quick answer!

I experimented a bit with your solution, and it seems to work for now, but I still need to register both routes (MapPageRootRoute and MapContentRoute), otherwise EPiServer's UrlResolver doesn't translate {company} as part of the URL, but rather just as a standard parameter (/?company=...), which is incorrect. Is the expected solution to register the route for both the root and the startpage?

Current solution:

routes.MapPageRootRoute(
    "selfserviceRoot",
    "SE{company}/{node}/{partial}/{action}",
    new { action = "index" },
    new { company = @"\d{8}", node = new ContentTypeConstraint<SelfServiceBasePage>() });

var urlSegmentRouter = ServiceLocator.Current.GetInstance<IUrlSegmentRouter>();
urlSegmentRouter.RootResolver = sd => sd.StartPage;
var parameters = new MapContentRouteParameters
                 {
                     UrlSegmentRouter = urlSegmentRouter,
                     Direction = SupportedDirection.Incoming,
                     Constraints = new { company = @"\d{8}", node = new ContentTypeConstraint<SelfServiceBasePage>() }
                 };

routes.MapContentRoute(
    "selfservice",
    "SE{company}/{node}/{partial}/{action}",
    new { action = "index" },
    parameters);

base.RegisterRoutes(routes);

As a side note, I currently carry the RoutedValue for {company} around by extending the Urlhelper:

//public const string SE_NUMBER_KEY = "company";
public static string PageUrl(this UrlHelper urlHelper, PageReference pageLink, object routeValues)
{
    var routeValueDictionary = new RouteValueDictionary(routeValues);

    var se = m_httpContextService.GetFullSeNumber();

    if (string.IsNullOrWhiteSpace(se) || !(pageLink.GetPage() is SelfServiceBasePage))
        return urlHelper.ContentUrl(pageLink);

    routeValueDictionary.Add(Constants.Routing.SE_NUMBER_KEY, se);

    var language = routeValueDictionary[RoutingConstants.LanguageKey] as string
                   ?? ContentLanguage.PreferredCulture.Name;

    return PageUrl(urlHelper, pageLink, language, routeValueDictionary);
}

//m_urlResolver = ServiceLocator.Current.GetInstance<UrlResolver>();
public static string PageUrl(this UrlHelper urlHelper, PageReference page, string lang, RouteValueDictionary routeValues)
{
    var virtualPath = new VirtualPathArguments { RouteValues = routeValues };
    return m_urlResolver.GetUrl(page, lang, virtualPath);
}

Ok, I did not understand that you also wanted to generate urls in that format, I though you just wanted to be able to handle incoming request. in that cas just change the SupportedDirection in the registration to Both, as:

var urlSegmentRouter = ServiceLocator.Current.GetInstance<IUrlSegmentRouter>();
urlSegmentRouter.RootResolver = sd => sd.StartPage;
var parameters = new MapContentRouteParameters
{
    UrlSegmentRouter = urlSegmentRouter,
    Direction = SupportedDirection.Both,
    Constraints = new { company = @"\d{8}", node = new ContentTypeConstraint<SelfServiceBasePage>() }
};

routes.MapContentRoute(
    "selfservice",
    "SE{company}/{node}/{partial}/{action}",
    new { action = "index" },
    parameters);

Ok, thanks once again. Out of curiosity, If you have several sites, will this route be registered for all startpages?

Yes it works for all sites. The root for the router is determined by a delegate that's get called for each request meaning StartPage is resolved from the host of the request.