RaMa Hey thanks a lot for your ideas and the awesome explanations! I tried the uxa thing and now I haven't managed logging in anymore. The screen freezes as soon as I hit enter after password entry. Switching to a text console doesn't work either because my password contains an umlaut.
Just for curiosity: do you think it's likely that the machine has a hardware problem that the bios hardware check doesn't notice? I mean the machine ran fine for months until four weeks ago!