Ok, in the meantime I indeed worked out a solution for a navigation menu with a partial view and a custom controller. Here it is. I am going to document it like a good boy so other Umbraco 6 / MVC n00bies may benefit.

1. Create the Model

Since I wanted to use a strongly typed view I created a Model object called MenuModel. Put the MenuModel class in the Models folder of your MVC project.

using System.Collections.Generic;
using Umbraco.Core.Models;

namespace PatentVista.Models
{
    public class MenuModel
    {
        // My Model contains just a set of IPublishedContent items, but it can
        // contain anything you like
        
        public IEnumerable<IPublishedContent> Items { get; set; }
    }
}

2. Create the Partial View

The partial view is called NavMenu.cshtml and receives a MenuModel object. I put NavMenu.cshtml in the Views > Shared folder of my project.

@inherits UmbracoViewPage
@{
   Layout = null;
}
<ul> 
    @* Iterate over the items and print a link for each one *@
    @foreach (var page in Model.Items)
    {
        <li><a href="@page.Url()">@page.Name</a></li>
    }
</ul>

3. Create a SurfaceController

Now create a custom Controller in the Controllers folder. Mine is called NavMenuController. Not sure if the controller and view name have to match (the beginning at least), but I chose to match them.

using System.Web.Mvc;
using PatentVista.Models;
using Umbraco.Core;
using Umbraco.Web;
using Umbraco.Web.Models;
using Umbraco.Web.Mvc;

namespace MyProject.Controllers
{
    public class NavMenuController : SurfaceController
    {
        public ActionResult Render(RenderModel some)
        {
           // Get the current homepage we're under (my site has multiple, because it is multi-language)
           var currentHomePage = CurrentPage.AncestorOrSelf(1);
           // Create model object
           var menuModel = new MenuModel();
           // Select descendant "Artikel" nodes of the current homepage and set them on the menu model
           menuModel.Items = currentHomePage.Descendants("Artikel").Where(x => x.IsVisible());
           // Return the partial view called NavMenu
           return PartialView("NavMenu", menuModel);
         }
    }
}

4. Call the view from anywhere

Now you can call the navigation menu from anywhere with this line of code:

@Html.Action("Render", "NavMenu")