Thanks for the tip! I ended up spying on the MenuFilter: I created a Filter in my module that added my additions to YOURZONE via WorkContext.Layout.YOURZONE.Add("Foo", 5).
Downside: difficult for other parties to implement (they would have to create filters instead of being able to attach parts), and it gets called for each and every request (which is what you want for the navigation, but not for my module).
I'm now trying out a new approach: converting my LocationDetails object to a shape, and rendering that using the orchard rendering engine.
var contentItem = _contentManager.New(ContentPartNamingConventions.ApplyTo<LocationDetailsPart>());
var ldr = contentItem.As<LocationDetailsPart>().Details = details;
return new ShapeResult(this, _contentManager.BuildDisplay(contentItem));
Hopefully I'll be able to dynamically create a contentitem that doesn't exist in the database, and render it using Orchard. Haven't got it working yet, though, but I'll keep you updated.