This does sound feasible to me but I've not attempted to do it before. It
will present a significant amount of work. You may want to do a Proof Of
Concept (POC) and some extensive testing to ensure you have all the pieces
in place (especially security) before putting too much time into your server
control.

Also, I'm sure you know, existing SharePoint Portal server  Portals will not
likely accept the changes to the underlying Site Definition.

Any other ideas for customizing  portal navigation? Specifically, we'd like to add  some links into it that are more manual (ones we can say, point to 'google.com' or a different URL).

My first test  (creating a simple server control  and adding it to the default.aspx) that just wrote out the current date as well as iterating through all the top level areas on the current portal  worked just fine... pretty quick test. The only unkown I was real concered with was adding a server  control without having access to any codebehinds in the SharePoint templates.

But you're right, I do want to test like a crazy person and need to add some security checking into it as well... prob some sort of caching routine so I don't have to traverse the tree every time.

well i tried it in the most simpliest way using
FP2003.
I don't feel anything went wrong till now. I was able
to add  new links or delete the existing one etc.

Can anyone suggest me if I am doing somehting wrong on
this?