One of the problems with memories and their compatibility with various systems is that when they are run at high speed - such as 400MHz DDR or 800MHz DDR2 - the margins are wafer-thin. And variance isn't just in the memory sticks, but also in the connector, the motherboard, the memory controller and the processor itsef. If you have a particularly slow pad on one pin on the memory controller, the memory can be will within margins, but still won't work on the system.
I had a memory problem with a Xen virtual machine - the memtest86 that comes with most Linux distro's would run just fine running alone [that is when booing directly into memtest86], but when running a virtual machine in Xen, it would fail to read that memory - just one bit was wrong, and I even wrote my own little version of the particular test in memtest86. Changing the memory to another two sticks of the same brand fixed the problem. Obviously, running with virtualization enabled changed some timing in accessing the memory - perhaps it did some page-table fetching that didn't happen during the normal run, for example.
And yes, it can be difficult to find memory errors, because other interference can cause problems to come and go.