I would not have thought this is anything to do with the way the Custom Menu works, that's if you are adding the URLs via the section in Site Administration > Appearance > Themes > Theme settings.
The syntax for this is:
so you would have something like this...
Google|http://google.com|Google search Engine|en (this last section is only useful if you use different languages)
The highlighted syntax below changes to HTML like so...
<a href="http://google.com" alt="Google Search Engine" >Google</a>
And so it is a normal link.
However if the links are attached to URLs inside a course then anyone NOT logged in will need to login. This is if I am understanding what you are saying.
If not can you send me a link to your site to see what;s happening?
Phil, I have just tried the URL you added and find that the stelth of your firewall is preventing me to open the page, so it looks like an internal server problem probably due to you having https: security settings.