By the way, I usually put my links in a list, but I don't really see why I should ALWAYS do it. The only advantage it would give me here is being able to use top padding instead of relative positioning, which in my opinion isn't worth putting in all the extra HTML.
Just a note, the reason for using a ul really isn't anything to do with having some helpful container for CSS; otherwise you'd just use a div like everyone did in the Bad Old Days. It's more for reasons of semantics and user agents who can present something as an ordered or unordered list of links.
Whenever I have a group of inline/floated things and they only just fit in some browsers and wrap in other browsers, I either have to enlarge my container, reduce the number of items or make each item smaller. However since we don't have enough code to know 100% if font variation is the problem, we can't say for certain that those are your only options.
But I usually would hit similar issues back when I stated uneven fonts in a font-stack, like
verdana, arial, helvetica, sans-serif;
because the difference between having verdana and not was huge. I don't list fonts like that anymore (this likely isn't your problem since all your test browsers are on the same machine).