Stumbled across this old question, and I'd like to offer this tidbit of wisdom:
If you add the navigation nodes programmatically (like with PowerShell or C#), they will be security trimmed. Navigation added manually via the UI, however, is not.
Here's an article showing how to add nodes with PowerShell: SharePoint 2010: Security trimmed navigation
The basic code looks like:
using (SPSite site = new SPSite("http://theurl/tothesite"))
SPNavigationNodeCollection nodes = site.RootWeb.Navigation.TopNavigationBar;
nodes.AddAsLast(new SPNavigationNode("Title", "/siterelative/url"));
Or in PowerShell:
$web = Get-SPWeb "http://theurl/totheweb"
$nav = $web.Navigation.TopNavigationBar
$newLink = New-Object Microsoft.SharePoint.Navigation.SPNavigationNode -ArgumentList @("Title", "/siterelative/url")
Hope this helps someone down the road.