Html.Routelink generates different URLs when locale changes

Question

My website can be read in Dutch, English and German. Users can select the language they like by clicking the flags on top of the page. The links are rendered like so:

<ul class="nav navbar-nav navbar-right flag">
                @if (Request.IsAuthenticated) {
                    if (model.AvailableLanguages.Contains("NL")) {
                        <li class="flagNL" title="Nederlands">@Html.RouteLink(" ", new { locale = "nl-NL" })</li>
                    }

                    if (model.AvailableLanguages.Contains("DE")) {
                        <li class="flagDE" title="Deutsch">@Html.RouteLink(" ", new { locale = "de-DE" })</li>
                    }

                    if (model.AvailableLanguages.Contains("EN")) {
                        <li class="flagGB" title="English">@Html.RouteLink(" ", new { locale = "en-GB" })</li>
                    }
                }
                else {
                    var qs = (!string.IsNullOrEmpty(Request.QueryString.ToString()) && Request.QueryString["ReturnUrl"] != null) ? Request.QueryString["ReturnUrl"] : string.Empty;

                    if (model.AvailableLanguages.Contains("NL")) {
                        <li class="flagNL" title="Nederlands">@Html.RouteLink(" ", new { locale = "nl-NL", ReturnUrl = Server.UrlDecode(qs) })</li>
                    }

                    if (model.AvailableLanguages.Contains("DE")) {
                        <li class="flagDE" title="Deutsch">@Html.RouteLink(" ", new { locale = "de-DE", ReturnUrl = Server.UrlDecode(qs) })</li>
                    }

                    if (model.AvailableLanguages.Contains("EN")) {
                        <li class="flagGB" title="English">@Html.RouteLink(" ", new { locale = "en-GB", ReturnUrl = Server.UrlDecode(qs) })</li>
                    }
                }
            </ul>

I fail to see why this leads to 3 different base URLs being rendered. When I browse the website in German, the links are:

For Dutch: webserver.local/?ReturnUrl=%2F
For German: webserver.local/de-DE/Account/Login?ReturnUrl=%2F
For English: webserver.local/en-GB?ReturnUrl=%2F

The biggest issue is when I click Dutch the site throws an error, HTTP 401 - Unauthorized. A smaller issue is the deeplink getting lost when the language is switched. Any suggestions would be appreciated.

Edit: And the requested RouteConfig:

public static void RegisterRoutes(RouteCollection routes) {
            routes.IgnoreRoute("{resource}.axd/{*pathInfo}");

            routes.IgnoreRoute("favicon.ico");

            State state = new State();

            routes.MapRoute(
                name: "Localization",
                url: "{locale}/{controller}/{action}/{id}",
                defaults: new { locale = "nl-NL", controller = "Home", action = "Index", id = UrlParameter.Optional },
                constraints: new { locale = "[a-zA-Z]{2}-[a-zA-Z]{2}" }
            );

            routes.MapRoute(
                name: "Default",
                url: "{controller}/{action}/{id}",
                defaults: new { controller = "Home", action = "Index", id = UrlParameter.Optional }
            );
        }