I did boot from CD a few times, if only to try the repair-option. No help, the behavior remains.
The problem appearing at the same time during startup doesn't seem to be memory-related, does it? I'd think a memory-bug would make itself noticeable randomly.
I managed to get the computer started a couple of times, but only after waiting at above mentioned point for 10(!) minutes. Even then, some things like display tab, start if IE are veeeery sloooow...
Still confused... what on earth is it looking for 10 mins long???