Interesting behaviour that I saw yesterday.
I had a MOSS 2007 site with a custom permission level defined on it. The users that had this permission level didn’t see the site on the top navigation bar, but if they entered the site by the URL they could enter it without troubles.
The solution was to add a “View Elements” permission to the custom permission, too. After that the site showed correctly on the top navigation bar.