I think I found the problem: it was a defective ram stick. The laptop
had 2 dimms @ 512mb each. I pulled one out and ran memtest 86 on the
other. One of the sticks produces multiple errors within one minute
of the start, the other ran for 2 hours with no problem.

I guess I will need to buy new ram.

I still wonder what caused the weired artifacts in the BIOS thought
and how that is related to the memory problem.