I fixed this by throwing more processing power at it. Got a desktop machine with Intel E8500 Core2 duo 3.16GHz and some 800MHz DDR2 running Windows XP. Simulations that took a half hour on my laptop (Dell Latitude D620 with Intel T7200 Core2 duo 2.0GHz) take 10 minutes on the new system. I did also try Modelsim and that is nice and fast for functional simulations but what I really needed were timing simulations. It seems that I'm clocking some parts of the design too fast and in other parts not waiting long enough between feeding input and reading output. None of these problems become apparent in a functional simulation, there everything works ;)
Only problem is that the web edition license from Altera doesn't allow "terminal server" use so I have to use VNC to control the machine instead of Remote Desktop (I don't have space for another monitor on my workbench so I'm still working on the laptop)