HP/Compaq dictates that only specific memory modules (e.g. 256MB module P/N 285523-001) may be installed in my laptop (costs around $200 and requires return of a defective part).
I went to the Kingston and Crucial (Micron) websites and selected the proper laptop model and got a list of memory modules that are guaranteed to be compatible with my laptop. These modules seem similar to generic modules of the same specification (DDR SODIMM, PC2100, CL2.5, 266MHz) but much more expensive (compare for example Kingston's KTC-P2800/256 at $42 with their own KVR266X64SC25/256 at $27).
I finally opted for a used generic memory module (at 15$). I got it from a friend of one of the sys-admins at work, with a promise that if it didn't work I could give it back to him. So how does one make sure that a memory module is functional? - well, it's quite easy:
- install memtest86+ like this:
apt-get install memtest86+
(this actually installs a new "kernel" that's dedicated to memory testing)
- shutdown the PC
- install the memory module (and yup - firmly push that sucker into its slot)
- turn on the PC - enter BIOS
- make sure the memory module is detected correctly (note that some memory may be used by the graphics accelerator, so that the reported memory size may be a bit smaller than expected)
- exit BIOS, and select memtest86+ from the GRUB menu
- memtest86+ starts testing memory automatically
- wait for it to complete at least one full test with no errors (takes about 40 minutes on my laptop with 512 MB)
- exit and commence with normal boot