Using the single site version, I have the same problem.
I'm placing my links like this:
<li><a href="/toerisme/brochures/nl">Brochures</a></li>
When I click on it, in IE i go to "about:blank/toerisme/brochures/nl" when the menu is in lazy mode, when it's not, then i go to http://www.mysite.com/toerisme/brochures/nl
It works great in firefox btw.
I need to place the links relative because when the user doesn't accept session_cookies, PHP only will add the SID to the relative urls.