I was able to reproduce the problem. What we're running into is the following "quirk" in IE: http://support.microsoft.com/kb/262161 - after the first 30 style tags on an HTML page, IE ignores the rest.
I was able to prove this by hand editing a page and simply combining the styles into fewer style tags.
So where are the styles coming from? It's all of those numerous popup menu controls when you're in standard (album) view - add enough albums and sooner or later this problem will appear in IE.
I built my own version of the component that hides the menus in standard view, and it resolves the problem as well.
Matthias (I hope you see this) - this is something to watch for going forward as well, and perhaps to notify the main team. It looks to me that the menu styles are being generated in the core, not in the gallery code - thus this represents a fundemental limit on the number of menus you can use on a page. Unless (as I expect is likely), there are ways to avoid it (say, by using a style sheet and class - I haven't dug deeply enough into the menu system to know if there is a better solution).
Also, the private version I created also solves the friendly URL issue with the current version. I know you're focused on the new gallery (which is fine, that's why I like open source). But if you have any interest in the modifications I've made, I'll be glad to send them along.
Dan