MEMTEST or MEMTEST86+? The latter is what I recommend. No it's not infallible. It's hard to subject memory to all the possible conditions it will experience while running Windows. Generally it's a good test though, but it's possible to get a false pass.
Most people don't bother to match their memory to their mobo, and then go through what you've been through. This forum is littered with posts like that.
Modern mobos are VERY fussy about RAM timing. I always recommend that my clients buy memory from a vendor with an online configurator that allow you to lookup the exact match for your mobo or system. Gone are the days when you can just order whatever Corsair or Geil RAM is on sale at NewEgg and expect it to work reliably in every mobo. Sure, you can probably tweak your memory settings to make it work (assuming you don't have an OEM system) but who needs the hassle?
As LiLithTecH pointed out there could also be an interaction with another hardware deivce that's not testable by MEMTEST. You video card isn't working very hard during MEMTEST. The RAM may pass the test and even be stable in the desktop, but if you play a 3D game and start drawing more power and flood the data bus with the enormous amount of data required for the video card, the memory timing may go to hell, or the voltage from the PSU may drop to the point where your memory has an issue with it.
A computer it a large collection of interdependent systems.
If it seems to be rock stable with the memory you're using now I'd stick with it if it's the right size.
